Do you have any other power line devices?
I had a set of "wireless" intercoms that wreaked havock on the X10 signals. Seems the wireless part was through the wires after all. After I eliminated them the X10 stuff works :)
Additionally other things to look for are Motors, and some older flourescent lights.
In a nutshell, try to isolate the cause by turning things off ...