I already own the Clip+ and was going to buy the Clip Zip, but I ended up getting the Fuze+ instead.
(I figured if I was going to upgrade, I may as well do it properly)
What you've heard is correct. It is horribly slow with the original firmware, but this is because of the firmware, not the processing speed of the player itself.
I've found it to be very good with Rockbox, however keep in mind that there is still a lot of work to be done.
If you're prepared to wait for development, then it's a great player, but don't expect everything to work perfectly out of the box.
The port was recently moved from "unusable" to "unstable" which is a good sign, and development is definitely active, it's just slow.
The Fuze might be a good idea as I believe that the Rockbox is stable.
To summarise, the navigation is flawless with Rockbox, but not everything else works 100% (yet)