I'm having exactly the same issue!
Installed Nookie on SD card last night, had a little trouble sorting out adb but eventually got all the apps pushed in.
WiFi's on, browsing is fast and stable. I thought it might be a problem with it going to sleep and losing the connection, so I set the screen-off delay to 10 minutes. That didn't help.
Interestingly, it's not only a problem with the market. I tried setting up my gmail account, and it's the same sign-in procedure, with the same error. Googletalk, same thing. I set up my Hotmail exchange server just fine, though.
I remembered something about signing in to YouTube when rooting the NC, so I tried that, but the YouTube app doesn't work. Have you tried yours? It opens, goes to black screen, then closes right away. I haven't tried wiping the data for YouTube yet.
As soon as I get home tonight I'm going to reburn the Nookie image and start over. Will let you know if that works.