After the rather lackluster first 2 weeks, we got an inquiry from one of the big names on the App Store: Lion Studios. They specialize in partnering with indie developers who create good games but have no idea how to promote them.
They gave us an offer to buy the game from us, start promoting it heavily and give us a certain percentage of its lifetime revenue.
After some negotiations we took the offer, transferred the rights and the app took off...