@Michael and Giles...
Michael - my 3G jesus phone has Bluetooth but its not that great... not managed to connect it to much as yet. New firmware out Friday tho that I am hoping will improve that (plus speed in the contacts list and notes applications!)
Giles - the Nike+ also only records footfalls/number of steps. But it uses a preset average step distance and number of steps per second to work out speed and distance (you can configure these by running a set distance on a treadmill and also doing it walking as the Nike+ is able to tell if you are walking/running depending on a steps/second threshold I presume). So anything with an accelerometer and the relevant program calculating these things could do the same.
Pretty nifty though either way and I used teh Nike+ a lot when I had a nano... I just wish I could plug it into my iPhone to do the same, or an app is developed... or I will just get a cheap 2gig old nano to go running with (probably safer too in case I dropped it/came out of the arm holder)
Garmin forerunner is a great tool, for the serious runner or if you got some spare cash. The nike+ is only £20 (and you dont need to buy special trainers, just tuck the unit into a small bag and tuck it under your laces...) and for me it was pretty accurate. Fun fun fun...