There are two phases coming into your breaker box. In a row of breakers, the first breaker is on one phase, the second on the other, the third on the same as the first, etc. (We're counting full-size breakers only -- if you have a split breaker with two switches on it, the entire breaker is on the same phase.) When you have a ganged breaker (two strapped together) you will find they are for a 240V appliance such as a dryer, A/C, stove, water heater, etc., and are making use of both phases (that's why they alternate on the bus).
Now, if the sending unit and the receiving unit are on the same bus (you'll have to count breaker slots), they ought to work great. If they are not on the same bus, they might or might not work. Newer equipment using newer protocols have better chances.
Two things you can do to fix this.
One, take one of the breakers involved and swap it with the breaker above or below it. (They pull out and plug in without you having to touch anything live. Don't play with the feed wire, just move it with the breaker.) Try to exchange it with a breaker of the same value, because sometimes the electrician has carefully balanced the load on each bus. (Don't forget to swap the labels when you're done.) That way they will both be on the same bus. (Obviously, if you have more than two networking units to coordinate, this could get pretty involved.)
Or, install a bridge product, which is made to pass non-power signals between the two buses.
This one is made for Insteon units, but I suspect it may work equally well for powerline ethernet.
In general,
this page contains a great discussion of the issues in powerline networking