On the bottom of the Featured tab Apple ID is correct, but when I try to update an app App Store asks me a password for the old Apple ID that I no longer have.
You bought the apps with your old Apple ID. Apps are permanently tied to the ID with which they were bought.
I'm fairly certain if you deleted them, and re-downloaded them with your new ID, the problem would be solved. You would, however, have to pay for them again if they were not free.
Attempting to update app asks for a different iTunes account password (pretty much a duplicate)