Trying to connect to third party RDP but can't connect.

So I have an issue where our client signed up for a "cloud software" solution. Which is they run a VM on Windows with a Line of Business app and give you access through RemoteApp via RDP.

I am trying to connect to the third party RDP but it is constantly failing. Their support says that there is a problem with our network configuration. Which I find odd, since we are running their router/firewall in a pretty default state.

They say they need port 80/443 open so clients can connect over RDP to their hosted app. But no matter what I do, I can't get it to connect and I am running out of ideas.

What works:

1) I am able to add the url into RemoteApp and get it to connect.
2) It will accept the username/password when adding the RemoteApp URL
3) I shows the links to the RDP connections in the folder.
4) When I click on any of the links, it says that it can't connect and to contact the network administrator.

Things I have done so far:

1) Open ports on Windows firewall.
2) Used ping, Test-NetConnection to make sure computer can connect to their RDS server. Was able to successfully connect over ports 80/443.
3) Had them change the username and password on account.
4) Had the client set it up on a non-domain joined machine at home (they got it to work) and bring it in to the office to test (as soon as they connected to the office network, it stopped working.
5) They have port 80/443 set to redirect from their WAN IP to their RDS/Anywhere Access server so they can remote into their work computers from home. Removed these rules and retested with same results.

I feel like our clients firewall is the main culprit over any server config. But I can't think of anything else to test since the work computer is able to talk with the third party RDS servers over port 80/443. Nor do I have access to the third party cloud providers servers to review their logs.

Any help would be appreciated.