ne-nor, from what I recently discovered, it's quite simple.
The App Store and iTunes Store take over the system language of your computer (Mac or PC).
Normally I speak Dutch, but for practicing my French (I have exams in French in the near future) I switched my system language to French.
When I connected my iPod and synced it, afterwards I discovered the App Store was also in French, while the rest of the interface of my iPod remained in Dutch. iTunes on my Mac, was in French (since that is the system language), and so is the iTunes Store.
Hope this relates to your question. It's not a definite answer, but deleting iTunes might diminish the chance to change it to another language...
Possible suggestion: re-sync the device to iTunes when making sure your system language is in English.
It can be found somewhere in the Control Panel or System Preferences, then International (Mac) or Regional and Language Settings (Windows). Just out of the mind...
Hope it helps.