I upgraded my iPhone 4S to iOS 5.1 yesterday, and when I run the Nomad app I get the AR/3004 validation required error. It seems that whenever iOS is updated you need to delete and reinstall the app. They couldn't have fixed this by now?
Oh also same thing when I upgraded my phone from 3GS to 4S. The backup restored on the 4S, and the Nomad app wouldn't work until deleted and reinstalled.
I ran into the same issue restoring my iPAD 2 backup onto the iPAD 3. Had to delete and reinsall the app and then the authentication worked.