Help Purchased apps not appearing in market place after phone swap.

Today I had to swap out my Droid for a new one due to radio issues. After going through the initial setup of the phone I when went to download the apps I purchased from the market place and they did not show up. Not only were they not listed, I could not even search for them. The biggest one for me was MyBackup. From the store, I can download the trial, but there Pro (paid) edition does not show up. From the app itself, if I select buy, I get an error stating that the app cannot be found. I have about $50 worht of variious apps now that I cannot access on my new Droid. Apparently, this is widespread.

Missing purchased applications after firmware upgrade - Android Market Help

Has anyone else run into this and if so, were you able to get your apps back?