Easiest way would be to have two copies of each theme, one with and one without the ads, not ideal, but easiest.
Other than that, you could investigate hacking a plugin such as " ozh_who_sees_ads " and making it work alongside a custom user field at registration (paid or not paid).
Thinking as I go along here ... or you could use a plugin like s2subscribe to have (in the case of this plugin) up to 4 user subscription levels, and combine that with "member access" or "members only" (and a little hacking) to determine which themes they can see in their back end as sub-blog admins.
On a similar route, you could have a site-admin managed "themes blog" and depending on their s2subscribe/member access settings, they get to see one set of themes to request if they haven't paid, and a different set if they have paid (allows you to offer themes unique to the payers too, if you do it that way). Of course, this makes it a little more "hands on" for the site admin, but it means no custom code or hacking is needed.
Just a few ideas
Gaz