Google most likely has automated systems which scan your app store screenshots for copyrighted material. Depending on how you are using the images, you are probably covered by fair-use provisions of U.S. copyright law, in which case you do not need permission. Have a quick read up on it and work out if your case would come under it or not and then appeal to Google, giving them your reason and state that law.
I think the main problem here is technically you are using copyrighted to material to advertise your app via the app store screenshots. So even if you can use the cover art in your app under fair-use, you still wont be able to use them in your public screenshots as they may consider this advertising.
Maybe pick a few publishers you like and email them direct and ask if you can have permission to use their covers in your app screenshots. They may give you permission.