You answered the one question I should have written differently!!
The question should have been - Did they offer to shop your music for a fee without ever hearing your stuff?
Even still, if you've got somebody interested in your music, the fee they charge should be contingent on whether they make you any money. If they say "Give us $300 and we will shop your music to all of the artists/agents/managers/etc. in Nashville" that is not the way to go. I could do that. You could too.
If you sent your stuff out to some people and they are offering to promote/shop you based on a percentage of any deals they bring you, that sounds legit.