First of all thank you for using Responsive Theme, you rock!
Ah the logo situation, actually there's no issues with WordPress logo uploader, when I said WordPress and not the Theme itself is because we're using custom header feature by WordPress for our logo.
All right, when saving a logo, or any other PNG image make sure that the its saved correctly:
- No Matte
If your PNG image isn't saved like that, you'll have the fuzzy border around and poor image quality.
Also, you mentioned JPEG, no it doesn't have to be JPEG, you can use PNG, GIF or anything else you think that it might work.
This is coming from the guy who started working on Photoshop much before I did in WordPress.
By the way, if you have any questions, please visit our free and dedicated support forum.
Best of luck and thank you so much for using Responsive Theme!