1. Yes, they could connect before - this problem has arisen in the past few weeks.
2. We only have VC 3G. Just to be clear - all can connect to the VC network, it's just when users are allocated an address in the 10.x.x.x or 41.13.x.x range that they cannot establish a VPN connection to our network. Other IP ranges eg 41.23.x.x work fine. This is not to say that there are not other ranges that will not allow a VPN connection - it's just that 41.13.x.x comes up so often.
3. Yes, I have checked this. As I mentioned earlier - the VPN connection does work, just not on the 41.13.x.x range.
4. Yes, completely standard - port 1723 (PPTP)