I had a similar issue with my updates via the App Store app always saying my Apple ID was not valid, yet I could login to the store via the browser.
The issue is caused by the very first boot when setup asks you to enter an Apple ID. Most people, including me, simple add garbage just to get past this screen so that we can quickly see our new toy in action.
Digging through the internet I found the fix in the most unlikely of places. Just change your Apple ID password as mentioned above and the problem magically goes away.