I don't work for Google so I can't speak to their method of sizing & compressing the images, but your image is very noisy which means that any modifications will significantly alter the sharpness of the textures you're using.
Noting that their guidelines warn that your graphic "will be downsized to mini or micro", and even in a desktop browser the art is reduced to a smaller size and transcoded into JPEG, you may want to think about simplifying your image if maintaining sharpness is important.
While editing your post, I noticed there is another link from Google with recommendations specific to Feature Graphics: http://android-developers.blogspot.com/2011/10/android-market-featured-image.html
Notice that they state the following:
Your image has to be designed to scale; it will need to look good both in a full-size Web browser and on a little handset. You can rely on the aspect ratio being constant, but not the size. Here’s a tip: Try resizing your image down to 1 inch in width. If it still looks good and conveys your brand message, you have a winner.
While you are currently focused on fixing the sharpness, you may want to rethink the entire graphic. Just fox example, here is how your graphic would look when converted to 240px width (not uncommon on an older 'droid):
The logo is good, but the other text is practically illegible.