My "old" P800 gave up the ghost: the keypad stopped working. I got pretty frustrated with it in any case -- the UI felt kludgy and the stylus wasn't that great for working with it. The scroll wheel was nice, but not enough to make up for all the other deficiencies. I briefly used a temporary, do-nothing phone with no computer synchronization, no Bluetooth, nothin'. The experience was not pleasant, just lots of flipping open the laptop just to get someone's number.
After seeing what Bryan Rieger is doing with Flash on phones, and the fact that only Nokia has licensed it so far, I decided to get a Nokia phone.
I got my new Nokia 6630 just yesterday, and am still figuring it out. This Loud Thinking blog post has lots of good info on why it's the Best. Phone. Ever... as well as linking to a lot of useful applications.
I'm also going to link to this page of Fido GPRS settings, since I had to re-enter them.
(Yes, I do have to wait until Tiger before it will sync with my laptop, but it's *really* easy to add contacts as people call)