What's touched upon in various ways in all the comments is that "PR" and "Media Coverage" is not the end all be all. In fact the successfully software startups I know STILL email individual potential customers on a daily basis.
I think one of the great myths of the internet is that you should just create a product, throw it up on the internet with some SEO and AdWords and the customers will come. Sure it might work for a few people, but by and large you are still growing a business. And you often grow a business one person at a time, hopefully later you can learn to scale sales.
Often what is missing from people's MVP's and business plans is how are you going to very specifically market to your target customers, and what the cost of customer acquisition is. If you can't identify a way to find your target customer, you're going to have a problem. Again, I don't think general SEO and SEM is going to work.
Don't give up on your idea, start emailing people. 50, 100 people a day. Convert them one at a time. If your business idea is not specifically just some sexy piece of technology, direct mail may work too (if you don't also have to educate people on why they need your product.)
Journalist want to write about what's hot, not about what is a potentially decent idea in a decent market. They want to talk about iphones, ipads, and facebook, and the latest jargon.
Anyways, start finding your target customers and email them. Don't worry about email campaign tools and crazy stuff, just starting email or calling them one at a time. Building a web based software business doesn't mean you can just skip sales.