Have you tried killerstartups.com? For about a hundred bucks you can get a few thousand pageviews. I used their service and was pretty happy. There are also other similar sites. They are not as effective but each would bring a few new subscribers.
Thanks for the suggestion. How did the conversion rate from killerstartups.com compare to ad campaigns, if you tested those as well?