Run highly targeted advertisements, and specifically include in the advertisement that you are looking for beta test users to talk to - and what kind of users you are looking for.
The most success we had was with LinkedIn Lead Gen forms. We got meetings with about 50 people at $25-$50 a pop. Be very personal and transparent - there are lots of somewhat bored professionals out there who would love nothing more than try out your app and give you feedback.
Another option is to sponsor a professional mixer event in your area. Depending on the event, you might be able to get a 5 minute speaking spot for less than a few hundred bucks.