I've found that building a relationship is crucial. I think a company blog can help with that a lot. If you're already publishing things, commenting on others' blogs and getting your name out there, bloggers are going to be much more receptive to you.
If you don't have time for all that though, targeting bloggers whose readers would be interested in your product is great. It's a win-win for both of you.