Unfortunately, the 0x0043 error code just means Xbox Live failed to create a connection, so that doesn't really help much in determining the problem.
Have you tried joining through the lobby, as well as by invitation?
If you have your online visibility set to invite only, try increasing it to friends only or public.
You could try clearing the cache:
- press and hold the Xbox button on the front of the console for 10 seconds until it shuts down
- unplug the power cable and wait 30 seconds
- plug the console back in and turn it on
- log into the same Xbox Live account you were using, start the game and let it sync, if required
Can you try switching either or both Xboxes between wired and wi-fi connections, if available? A couple people in the same household who got this error when trying to connected managed to fix it by having both Xboxes connect via wi-fi on a different network than the wired connection. Using a different network shouldn't be necessary if you are not on the same LAN, but maybe the connection method will make a difference, if you have not already tried that.