I just had my Legend HCx have the same problem. After talking to the Garmin people on the phone and trying assorted stuff, they agreed with me that the problem was with the unit. Since it was only 3 months old, they replaced it (with the help of Mountain Equipment Co-op where I bought it) right away.
Maybe call the Garmin troubleshooting hotline.
Nets