Two of my three Macs have been refurbed, and I'd recommend a refurb everytime.
My first refurb, my PowerMac 2GHz was a great deal at the price (about £500 cheaper than new) and is still working perfectly today - some 4 years later.
My current MacBook was a refurb too - and no problems here. I effectively got the mid-range model for the price of the cheapest model. Not only that but as a bonus my MacBook actually arrived with 2GB RAM instead of the 1GB listed - one of those things that sometimes happens when someone returns a Built To Order model
The MacBook is nearly 2 years old with no problems.
Oh and my first iPod was a refurb. It was a 2G iPod 10GB and came as brand new in box. It was an absolute crazy bargain at the time, and again works perfectly now (tho I've upgraded the battery) some 5 years later!
In short, order a refurb with confidence. As someone else pointed out - you get all the warranties etc you would with a new one, but you get the piece of mind that your actual Mac has been tested by hand - something that wouldn't happen with a new model, and so in my mind that makes it more reliable!