No SDHC should be fine, I have a 4Gb SDHC card in my Legend HCx, and prior to that an 8Gb one that I now use in my MP3 player. Both work perfectly.
Oh and now that I look both Sandisk so the branding is unlikely to be your issue. I've used lots of Sandisk cards over the last few years and have found them to be very reliable, yours is unlikely to be a dud but it's always a possibility.
Worth formatting it in something else such as a card reader, camera or mp3 player if you have one handy, then having another go.
Or maybe there's an equivalent firmware update for the Oregon, thought it was too new to need one but again worth checking.