Das wüsste ich auch gerne.

Außer ein paar seriöse Review Seiten anschreiben (die, die ohne Bezahlung schreiben) ist mir auch noch nichts Gescheites eingefallen.
Instagram kann funktionieren, wenn man schöne App Grafiken hat. Die Bilder kann man vor App Release hochladen und so hoffentlich einen mini Hype verursachen.

Alternativ (und hier plaudere ich bei Apple aus dem Nähkästchen):
schreib eine hammergeile App, die jeder unbedingt haben will.

Grundlegend hilft es z.B. eine App zu lokalisieren oder sie zur Universal zu patchen (falls noch nicht gemacht). Ansonsten:

Soziale Netzwerke/Medien nutzen
Eigene Homepage/Blog
App Store SEO
Werbung (z.B. bei einem Blog bei dem deine Zielgruppe zu finden ist)
Review Seiten (keine kaufen, per Email einen Code schicken)
App Store Eintrag überarbeiten (Icon, Screenshots, Name, Beschreibung,...)

Dann gibt es je nach App noch die Möglichkeit sich in Foren für die Zielgruppe dafür Werbung zu machen. Du entwickelst eine App für Grafiker, ab in ein Grafiker Forum.

Meine Erfahrung ist das du eine gute App brauchst, dann werden da auch irgendwelche Leute drüber schreiben. Verbreitet sich dann halt. Dinge wie die App bei AppGratis und Co. bewerben oder generell für einen Zeitraum gratis anbieten kann helfen, ich habe aber die Erfahrung gemacht das sich die Verkäufe innerhalb weniger Tage wieder auf den alten stand einpendeln.

Evtl. die App durch Updates optimieren/verbessern, aber nicht an deiner Zielgruppe vorbei entwickeln. Das passiert bei größeren Updates gerne schonmal - auch bei Apps mit einem "großen Namen". Ggf. kannst du dir Gedanken machen ob du nicht auf In App Käufe und Werbung umschwenken willst und die App dann gratis anbietest. Dann würde ich aber die In App Käufe nicht auf "entferne die Werbung" beschränken sondern Funktionen, Themes, etc. zukaufbar machen. Halt etwas was die Leute dazu bewegt einen IAP zu tätigen.

Wenn du die App aber schon in einem Stand hast wo du der Meinung bist das die so super ist und du nichts mehr dran machen kannst (Lokalisierung, etc) dann nutze die Zeit lieber für ein neues Projekt.

wenn eine app richtig gut ist, und sie auch einen nutzen hat dann verscheudere ich sie nicht für 99 cent
dann kann ich mir auch werbung, gute reviews etc leisten...

Wenn die Downloads explodieren sollen, dann müssen auf jeden Fall chinesisch und japanisch in den Lokalisierungen auftauchen.
(Ob traditionell oder vereinfacht kann ich nicht beurteilen, doch im Allgemeinen: je lokaler desto besser.)
Eventuell noch Lokalisierungen der Grafiken, Umgebungen und sogar Farben anstreben. (Rennspiel mit Rechtsverkehr in England? Schwarze Taxen in den USA? Rayman wurde ein hellblaues Oberteil für das Asien-Release verpasst, da sein europäisches lila Oberteil die Farbe des Todes in Asien repräsentierte. MItsubishi verkaufte den Pajero nur sehr schleppend im südamerikanischen Bereich, da es im spanischen/portugiesischen/brasilianischen umgangssprachlich für 'Wichser' steht und der Absatz ging erst nach oben, als der Wagen in Montero umgetauft wurde.)

Ich wette, dass diese Maßnahme das Budget bei Weitem sprengen wird. Deshalb ließ ich das auch außen vor.

Englisch, deutsch, chinesisch, japanisch, spanisch und französisch lohnen sich in der Regel immer. Hatte da irgendwo mal eine Rangliste, finde die aber gerade nicht mehr.

Was oben in dem Text noch fehlt ist: Spiele mit dem Preis und finde den wo du am den meisten Umsatz mit machst. Vielleicht lohnt es sich ja den Preis auf 1,89€ oder höher zu setzen. Wenn es aber x andere Konkurrenz Apps gibt die etwa das gleiche bieten kann man den Punkt aber schon fast wieder vergessen.