It was brand new out of the box...
You fully restored, and set up as new iPhone? If so, i'm even more confused.
When I got iPhone, i didn't restore before putting all my data in (stupid mistake). This causes the previous owner's apple ID to pop up every once in a while.