Alright, finally found someone who's also using Kindle 3G (3.1 software edition) and tested with the same picture.
http://rotar.tk/test.jpg
The picture is also shrunk so my guess would be that the Whispernet proxy server had some change recently to reduce the size of the images that are requested by kindles.
Is there anyway to cheat about the size of the image and actually get the original one?