Why's the pressing one key while you're letting up another a problem? Presumably it's either registering on press or release, but not both? Or is there more complicated fancy business going on?
If you type fast enough you'll often be pressing the second key with your other thumb before the first thumb has quite left the keyboard. The iPhone allows for this but the N1 doesn't (or doesn't appear to in limited testing).
The android keyboard is in fact multi-touch.
My primary issue with the keyboard is that it's very close to the four un-beveled buttons below the screen. I'll quite often hit "back" when I mean to hit "?123" which is pretty annoying.
I've also had good success with the new voice recognition feature for short emails and text messages.
Overall the keyboard is much less polished than the iPhone but I was pleasantly surprised at how usable it was.