If you have a 1,000+ users, hopefully some are linking to you. If not, it's probably time to do some link building.
Altavista is pretty good with showing backlinks. Just replace yourdomain.com with your domain and see what it brings up:
What comes up if you search Google for: site:yourdomain.com ? If that brings up anything, I doubt your domain is banned.
If it is banned, you'll need to file a reinclusion request with them. I'd be honest about any blackhat tricks that have been pulled and make sure there's nothing currently wrong with your site first (keyword stuffing, cloaking, sneaky redirects, etc...).
Relevant links from related sites would be best, but even submitting to directories would be a good start (if you haven't already).
Here's a good list of free directories you can submit to. That link will sort them by Google PR, so go ahead and start at the top and work your way down.
Also, it's nice to mix up your anchor text when linking. For example, Directory Critic would probably like the way I linked him here more than if I had just put the domain name or "Directory Critic."
Just avoid the automated submissions. Going from 0 to 10,000 links in 5 minutes doesn't look natural.
Matt Cutts is also a good source of Google info.
Save up to $96 at Dreamhost with ALMOST97 promo code (I get $1).
Or save $97 with THEFULL97.