Hi Habitat,
I have also experienced this problem. Generaly i would go back to the client and ask if they have a better copy of the logo. At some point in time they must have had the logo produced in a graphics application.
Failing this i agree with KCooper, try to have a play with it in PS to get rid of any fluffy edges and sharpen things up a little, without altering it too much.
It is difficult with logos as much of the time it is not possible to just add a border as the logo is part of the identity of the clients company. With in mind it would be best to stress to the client the importance of the quality of there logo on there site.
Can i ask, did you see the logo before you started and design the site based on it, or did you do the site first?
I always find that it is easier to have the logo first for a little insperation.
Hope this helps