Off the top of my head, three things come to mind here:
Firstly, like Clafou mentioned, you might be dealing with the XCode stale resources bug. Sometimes when XCode builds an app bundle, it sometimes includes older resources. So when you have changed or added resources, Xcode still doesn't include them or includes old versions. To verify this, ctrl+click the .app file that you submitted and see if the de.lproj file is included, and view it's content (drag it onto TextView) to see if it is the most up-to-date. If you have submitted an .ipa file, I think you can unzip it with winrar or something. And always click 'clean' before building.
Second, how did you test this? If you opened the app to see English, then changed your iPhone settings to German and then reopened the app, the app might still be opened and then the language doesn't change. If so, you should 'really' close your app first. Double tap the home button to get the opened app list, tap and hold your app and delete it from this list to force close it.
Last, you say it differs from the simulator. Did you test the app on a real device before sending it to the app store? The simulator might differ in behaviour for certain aspects when compared to a real device. It might not matter in this case, but still..