As your friend is trying to host, I would recommend they switch to an Open NAT type, or NAT type 1. Moderate can in some cases cause restrictions for players trying to host games.
Am I correct in assuming your connections are Mbps?
When did you first notice this issue occurring? and did anything noticeable about your internet connections change in that time?