Does call waiting actually not work or is it just the setting? The reason I ask what may seem like a dumb question is that on my iPhone 3G with AT&T, in the settings call waiting is turned off. When I try to turn it on it simply switches itself back to off while I'm looking at it. However, call waiting works on my phone without problem but yet the setting is off. I don't get the same error message as you but it just won't turn on in the settings.
If you can, It might be worth a call to your carrier. Call waiting is generally a function of the carrier and the plan. It used to be easy, if you had an iPhone in the states it was AT&T. In any event, it may have something to do with your plan and not the phone at all.