So I brought my car in again today to try and get this problem resolved. The dealership was told to do a deep level reset (Something about VIP level) but the Ford tech team. This I guess is different that the normal reset that happens when the software is updated.
Unfortunately it did not work, so now my dealer ship has ordered a new APIM to replace the one on my car. That will hopefully fix this issue.
The interesting thing I have noticed throughout all these resets a few things have not reset. Besides the iPod track info not changing back they AM/FM radio presets are still there, also my favorite buttons on the steering wheel still are set to what I had them at before the 3.0 update that wiped them out. There must be some part of the software that is not being touched by the reset.
The new APIM should be in later this week, hopefully this will take care of it.