If you done EVERYTHING in this post and has yet to solve the problem, THIS IS WHAT YOU DO. (Mac Users-Windows maybe)
Connect your iPhone to Itunes
Go to the Itunes store on Itunes
SIgn Out
On top of the STORE menu, is the LIBRARY menu
in LIBRARY-Look for APPS
in APPs, switch the view to LIST
in LIST view, right click on the first APP and click GET INFO
on the right hand side, its going to say PURCHASE BY
if purchased by you, click NEXT in the summary box
Keep clicking until you see the app purchased by this "Other" apple ID
Delete those apps
make a list of all apps you deleted
SIGN back on to the iTUNES store
Redownload all the apps
Then in the APP menu in LIBRARY drag your newly download apps on to IPHONE
Iphone will then replace the apps when you click SYNC
~ Problem should be fixed.
-Danny Vega