...I was keen to have a go without shelling out for a phone, or contract - I've been a happy PAYG customer for a while now.
I tried out a few Java apps - native apps for Nokia series 40 phones seem to be a new thing, I'll be after a 6300i when they surface. I tried eGPSTrack, GSPJ, Mobile GMaps, TrailExplorer, TrekBuddy. The one I ended up using was TMJ-Mobile - it has a lot of features, and a bit of a learning curve - but its stable.
Nokia's Sports Tracker looks interesting, other services I looked at include MapMyRide, MyCyclingLog, Bikely, OpenStreetMap, MapMyTracks - the most useful I've found is MotionBased. That and a bit of Google Maps.
TMJ also provide some Java based map creation tools for your PC. With these I was able to pull the cycle route maps from OpenStreetMap and stick them on my mobile - this actually stopped us taking a wrong turn into an industrial estate...