トレースの元画像がウェブ素材しかない場合

どなたかご相談にのって下さい。

主にビデオ制作を行っている会社に勤めているのですが、
ロゴ素材に関して現在進行形で困っております。
ロゴをトレースして使用しなければならないのですが、
そのトレース元になるものが
ウェブ素材しかないと言われてしまいました。
166×33pxのGif素材です。
これを640×480pxの画面サイズに合うように
引き延ばして使えとの指示が出ています。
カタカナの社名部分はどうにかなるのですが、
漢字部分が拡大するとぼやけてしまい、
もうどうしていいかわかりません。

営業に問い合わせてみたのですが、
「名刺もチラシもパンフもない、どうんかしてくれ」
と言われてしまいました。
MacOS10.2　illustrator10　で作業をしております。
いい解決法や対処法があれば教えて下さい。
よろしくお願いします。