I just had the same experience. The text would have been OK but the original background was captured at 1920x1080 at 72 dpi so the background wouldn't uprez well. Your graphic designer should redo the image (making it 2000 pixels or so) at a minimum of 300 dpi and save it as a Photoshop eps. Better yet have him make it in Illustrator and start with vector from the beginning.
fire*, smoke*, photoshopCS3
Charlotte Public Television
read up on live trace feature in illustrator starting with CS2.
I used this to convert an entrance banner for the Chicago Business Opportunity Fair. The original artwork provided to me was of an illustrative style of some Corinthian columns, so the results were fantastic.