We need to determine if there's a market for our new idea. Has anyone ever used a market research firm to determine that before? How much do they charge?
Don't use market research firms to research your idea.
That's knowledge you need to build yourself. Besides, deducting knowledge from information is in the eye of the beholder. There is just no chance that the market research company have the full knowledge of what you want to do, and therefor they're not going to make the conclusions necessary for you.
Anywhere from $100's to $100,000's or more.
Of course, that's a uselessly broad answer, but the question is like asking "how much do software firms charge to develop custom software," or "how much will it cost for a carpenter to build me something." There are so many research methods and tools -- surveys, focus groups, trials, you name it -- and the more you spend, the more you'll know.
Like many advertising and marketing agencies, we (Inedo Media) do a fair amount of market research to validate that ideas are worth the investment. It's more-or-less an insurance. On a $100K advertising campaign, it's easily worth spending a few $K to make sure the campaign is solid. On a $10K campaign, it'd be awfully foolish to spend that amount.
The same rule applies to what you're doing. How much are you considering investing (time + money)? If you're going to invest your life savings and two years of your life, then it's probably worth a several thousand dollar investment. If it's a hobby project that you're throwing a few grand at... maybe a hundred bucks?
Once you have a budget, then start contacting firms and see what they can do with your budget. If you're under their budget, they'll likely refer you to a little guy who can help.