ethernet cables are very cheap and you already had success in replacing one of them, so i think replacing more of them would be a good place to start.

i've only used the ethernet over power stuff once and it was dreadfully slow, so it sounds to me like you could be running into limitations with those. but it could also be that the cpu on your router is being saturated if you have a cheap and/or crappy one.