The advertisingIdentifier and identifierForVendor return "00000000-0000-0000-0000-000000000000"

It appears to be a bug in iOS. Seeing the same issue on devices that have been upgraded over-the-air, but devices upgraded with Xcode or iTunes work as expected without zeros.

Tried similar steps as you, and the only common theme was over-the-air (bad) versus tethered upgrade (good).

Update: Users that move directly from iOS 5.1 to 6.1 over-the-air experience a different behavior. Every time the app is closed completely and restarted, a new value is being returned by identifierForVendor. This would be expected if the app was being uninstalled and reinstalled, but that's not the case.

Apple confirmed this bug in their system in response to a Technical Support Incident request. They said that identifierForVendor and advertisingIdentifier sometimes returning all zeros can be seen both in development builds and apps downloaded over the air from the App Store. They have no work around and can't say when the problem will be fixed.