A simple workaround would be to strip the leading "www" using a redirect:
Code:
RewriteCond ${HTTP_HOST} ^www\.
RewriteRule ^/?(.*) http://example.com/$1 [R=301,L]
As for what's causing the problem, try typing in a URL that would be the final result of rewrites (eg http://www.example.com/final.php?city=New+York&state=NY ) and see what you get so you can check if it's the rewrite that's failing or something else. What's your real site? Not giving a real URL doesn't protect your site, it just makes it harder to help.