Windows works fine for me. Maybe you changed something somewhere. I had 0 problems.

Never changed anything on the phone. Fixed the issue though. I was using an older version of ADB: 1.0.31

Older versions don't support key RSA authentication.

I also had this problem.
Then I deleted some spare copy of adb.exe and its dlls that where installed under \windows\ by some "do-it-all" tool and updated the adb tools with SDK-Manager.
After connecting to the PC, my GNexus asked for confirmation before allowing USB debugging and since then everything is fine

I updated android sdk tools on my mac today (before that I couldn't launch abd sideload update.zip) and haven't noticed any issues with adb/fastboot commands.

AH, so it's the outdated ADB drivers playing up, perhaps good to mention in OP as a solution.

For me with stock kernel adb and fastboot ok.
I'm using bigxie rom deodex.

Originally Posted by rickbosch

AH, so it's the outdated ADB drivers playing up, perhaps good to mention in OP as a solution.

Done

It may seem obvious for some, but wasn't for me.
I flashed the upgrade, with the cable always connected then couldn't get adb to work. Just need to re-plug the cable for the prompt to show up

Is this new version in the latest Android SDK? If not, where can you get it from?

Originally Posted by EddyOS

Is this new version in the latest Android SDK? If not, where can you get it from?

Yes, it is in the new SDK.

On a side note, OP, the image you used and credited in the first post was mine, not manumanfred's.