Free Photoshop plugin to remove JPEG artifacts and noise.

Default settings were a bit too strong but it works pretty well if you tweak it.

http://www.topazlabs.com/topazlabs/03products/topaz_dejpeg/

There are examples on their site... I hope this helps!

Thank you, I'll give it a try.