We've actually had a lot of luck, but it's still really hard. We've been working on a site to help small startups to track/manage their interactions/promotions with the media (or at least help us do it, but we like to externalize our own tools).
For our successes, sometimes you luck out:
* We created bug.gd and the day we uploaded the logo to a random "Web 2.0" site, one of the moderators posted it on Digg, made the front page, and from there it scattered throughout the world.
* We mentioned bug.gd to TC a couple of weeks later (since the Digg storm imploded our site) and it was picked up by TC, Mashable, Lifehacker, etc.
* As people ran into us and heard about us, they spread the word around, and now it grows on its own, getting covered in PC World, and even local news coverage in random cities: http://blog.bug.gd/2008/11/08/buggd-coverage-on-wivb-buffalo...
* At Pycon last year, we did a lot of spreading the word by mouth and lightning talk. As an experiment, we released error_help() from the Python interpreter so that you could get help for your most recent exception from the rest of the world who may have run into it. Very few people used it, but we got a lot of interest from people who heard more than a few words about it all.
* For yumbunny.com (a dating site experiment) we mentioned it to TC the week before Valentine's day and they covered it. We issued press releases about it, though, and no one cared one bit.
* For tinyarro.ws, it spread through Twitter like wildfire because it was so odd (and shorteners are inherently viral) and it ended up with coverage on Mashable, Lifehacker, and zillions of blogs.
The only advice I can give is to make something either:
(a) Useful enough that people want to talk about it,
(b) Interesting/quirky enough that people want to talk about , or (c) be lucky sometimes (i.e. keep rolling the dice and trying until the die roll hits).
My best advice to you is:
* Try new APIs or new fads to get attention for yourself
* Seek partnerships that are mutually beneficial for popular sites
* Send not-too-uptight emails about your service to people you want to cover you. Try not to do form letters.
* Advertise on niche blogs or sites. While they may not give preferential treatment to advertisers, they will have heard of you so you don't end up in the spam folder automatically and you get their ear enough to say a few words.