Honestly I think most of what these low-dollar PR services do could be accomplished by the developer just posting a thread that they pay attention to on the TA forums. If a game can't generate interest here amongst our community, all the press releases in the world won't make people interested.
Honestly the best way forward is to join communities, post your game (don't spam), and really listen to customer feedback. Also, individually email review / blog sites with a link to itunes, screenshots, a web landing page and a trailer from youtube. Be brief and informative.
Also remember that marketing is tough and very time consuming. I've put as much time into researching marketing and listening to feedback as I did learning objective c and programming the game. So know that only half the battle is over when you submit to Apple (unless you get lucky).
For low-cost solutions I would recommend PRmac.com and iSpreadNews.com. iSpreadNews was actually a lot more useful than I had planned due to the fact that they put me in touch with a lot of international iPhone bloggers I would've never known about. I met some really cool people that way.
Last edited by Razoric; 03-23-2011 at 12:10 PM.