I have no experience in this other than the fact that I have done some research regarding the launch of a iPhone app for a previous employer. But seeing as no-one has answered yet I thought I'd point you to this: http://advertising.apple.com/promote/

I know nothing about the effectiveness of this platform, but from what I understand Apple will advertise your app to users of other apps. Hopefully that's at least somewhat helpful. :)