Hi there.
This is exactly, EXACTLY what happened to me when I switched to iOS 5. The problem is now solved, so I thought I would suggest contacting Expresslane, even though I still don't know what they did to solve it.
I was forced to create a new Apple ID (with an email address) when I updated my iPhone and as a result, was unable to update any of the apps I had previously purchased using my old account name. So, for example, for years I'd bought songs, apps etc. with "emd" and now my account was emd@yahoo.com. When I went to download a free update on my iPhone, I'd be prompted for the password for emd, which no longer existed, so of course my old password didn't work.
I went to the Genius bar, where they tried to help, but did not. Specifically, they were unable to find my old purchase history or the Apple ID associated with it (they found only the new one, since October 2011). So, the Genius bar guy submitted a request on my behalf to Expresslane. Expresslane emailed me that night with a list of all my Apple IDs and information about which ID was associated with all of my old purchases -- it was one the Apple store did not discover and that I did not even know existed. Let's call it emd@aol.com. It seems all my old purchases, back to 2006 and up to the iOS 5 switch were now linked to emd@aol.com, even though my iPhone was prompting me for the "emd" password.
I created a new password for emd@aol.com, signed into iTunes using that, and there were all my old purchases, including all the apps I wanted to update. I updated them, synced my iPhone, and I'm all set, albeit now with approximately 5 million Apple IDs.
Moral of the story is that Expresslane can help and it's entirely possible that the Apple ID that comes up in a prompt is not actually the Apple ID that is currently linked to the purchase.
Good luck.