A few things come to mind.
The centre autofocus point is by far the most sensitive on consumer cameras, it's sensitive to both vertical and horizontal contrast changes. Try forcing the camera to use this point only.
Is continuous autofocus on? Try turning it to single shot mode.
Are there any filters on your lens? A polarising filter will easily suck 3 stops of light - with f5.6 on the long end of a kit lens that will make it very, very hard for the autofocus. A linear polariser probably (although I've managed it :E) won't let you autofocus at all.
What conditions are you shooting in? Autofocus works on detecting contrast, bright sunlight creates the most contrast, dark interiors the least.
Which end of which lens are you using? Cheap zooms decrease their maximum aperture as they zoom in - they let less light in and that makes it harder for the autofocus. Try using the wide end - if it's a kit lens that's f3.5 and that's reasonably bright. f5.6 on the long end is quite dim, especially indoors!
Try popping up the flash to let autofocus assist work. If you have an external flash, stick that on, the autofocus assist lamp will work wonders.
Having said all that, it's weird that you can't get any shots other than on bright lights. Does sound faulty... Let us know how you get on with those suggestions

350D autofocus isn't spectacular, and certainly not with the kit lens (autofocus is largely dependent on the lens), but it shouldn't miss everything.