Sponsorships/etc are not something I feel the app is ready for. I feel those are something games with 1mil+ impressions/day do.
I have already ditched all of the Mobclix advertisers because of dating/etc ads and will be moving to another advert provider for my 15k impressions/day (and growing) which are currently served through admob. Just not sure who though !
The app in question is a Boggle-type word game with a bunch of extra's thrown to add a element of strategy. We payed a LOT of attention to addiction psychology to ensure the game is really compelling.
Perhaps if I added a "about you" dialog and asked for (optional) sex/age/zip code/etc to better target ads. I don't think anyone has done this before.... actually ask users to help them better target adverts !
With your particular challenge, as you hit higher audience levels, maybe think about sponsorships / branding opportunity where you can sell the 'eyeballs'. Since you are currently making nothing from the ads, maybe dump them and play around and give some sponsorships away as a trial to brands that you think are cool and well matched to your audience.
##
Second the comments on paying for extended play, but maybe instead of levels (which you say don't exist), pay is for extended time per day. (free 60 minutes cumulative a day, extended no daily limit)