Yeah. I ve been there. I used to face this problem when I used to try and sync up .ipa file that I created out of sdk 4.0+ with an iOS 3.1.2 based device through iTunes. Apparently, iOS 3.1.2 devices have some bug (or maybe it is in the iTunes) that the profiles don't sync up along with the .ipa file in them automatically sometimes.
But before that, you have to ensure that the iOS 3.1.2 device is provisioned with the profile in the first place. If not, thats the problem. If it is, then in such cases, I used to drag and drop only the provisioning profile first into the iTunes, then do a sync with the device (Nothing will seem to happen in this sync. This is for installing the profile into the phone.). Then drag and drop the .ipa file into the iTunes and then perform another sync. That used to work for me.
If you are facing this problem with the .app, then too you should try above. That should work.