iCloud account tied to random stranger's Apple ID

I just got an iPhone 5 on the release day (pre-ordered) and restored it from an iCloud backup (I had an iPhone 4 before this). I entered my Apple ID and password and it restored everything including my apps, contacts, and pictures. But then just when the restore was all done, it asked for an Apple ID and password again, except it defaulted the Apple ID to an entirely different email address. There are two problems with this: 1. There should be no reason to ask for my Apple ID and password again as the restore is finished - it keeps randomly popping up and asking for the password even if I click on cancel. 2. I have no idea where this other default Apple ID is coming from. It's not anybody I know, but it seems to be attached to my iCloud account somehow.

This is my second time seeing this person's Apple ID. The first time was when I got a replacement iPad (3rd gen) about a month ago and restored my iCloud settings on that. I was alarmed when I saw another person's Apple ID and assumed that it was the previous owner of the iPad since replacement iPads are typically refurbished units. I did my own investigation and emailed the Apple ID that was displaying, and the person said that she had never owned an iPad before but have had her account hacked before and someone bought a music album using her account. I got scared and notified the Apple Store and asked for another replacement iPad (still thinking the other Apple ID was tied to the hardware and not anything else). Only now after seeing this Apple ID on my iPhone 5, I realize that the extra Apple ID is probably tied to my iCloud account.

Please help me get rid of this extra Apple ID on my iCloud account.