8 hours sounds about right to me, I think mine does roughly that although I've never had to run mine down completely yet. In some places you can lose the GPS signal altogether, again not had that happen to me more than a handful of occasions. I will definitely agree with the machines taking a long time to lock on when switching on though, can be quite irritating, especially when your riding mates are all setting off and you are stuck waiting for it! A lot of these are just general issues to do with the GPS system though, the satnav on the car, and the a-gps on my phone can be just as temperamental.
On that thought, my Nokia 6220 Classic has Nokia Sports Tracker and Google Maps built in which almost makes the Edge redundant. So if you are looking for an alternative you might just need to upgrade your phone.