Here are a few ideas:
You have to talk to people
Network
Go out in the world and leave your computer to actually generate interest by talking up your product
Join the chamber of commerce, go to the events, get local interest.
Do some broad marketing with twitter, the radio, tv, local ads, signs, flyers, send out direct mail.
Narrow marketing, cold calling, PPC ads, setup meetings with people you "think" might have interest.
Pick up the phone, call a company you "think" might want your product - if they don't they may even tell you who does.
Call all your friends, their friends, their parents, their cousins and neighbors.
Think outside the box. Go viral with a video, a strange campaign, a giveaway, advertise on podcasts, or on blogs.
Email bloggers to review your product.
Ask your tweet followers to help you spread the word with a hash tag.
Create a page in Facebook, blab about it a little and have your friends help spread the word.
Go to info-sites in your niche and pay them to advertise.
Join some forums, be a voice, make some friends, and try hard to be a part of the conversation - not a spammer.
Post a beta/try me link to HN, Reddit, BoS, KillerStartups
----------
Or, you could put up a website and cross your fingers. (I'd cross your toes too if you're going this route)
Cold calling / meeting is tough in the beginning if you are introverted like I once was, but in my case the motivation to pick up the phone was knowing I would be able to put food on the table and pay the rent.
My first business was started when I had an idea for a software program and talked to a college professor. He put me in contact with another professor who just happened to know of someone in need of a software like what I envisioned. I agreed to write the software just how the customer wanted and they agreed to test. After the software was done, I began marketing it commercially and have since sold it in 56 countries.
Let me know if you need help with anything.
Any time you see someone swearing at a product, make note. That product sucks, whoever is using it wishes they could switch to an alternative. There's an idea. Sometimes it won't be as obvious as swearing. Sometimes it is just "it's so annoying that I have to submit all my material to colleges. There should just be an API for college admissions."
People talk about what they want constantly, you just have to tune in to hear it.