Hi Romeo,
Please ensure that the new certificate is installed in Computers personal store.
In addition, if the Gateway Server is running Windows Server 2008 / 2008 R2, please use RD Gateway Manager to replace the old certificate with the new one.
If the Gateway Server is running Windows Server 2012 / 2012 R2, you can configure certificate within Deployment Properties.

More information for you:
RDS: RD Gateway must be configured to use an SSL certificate signed by a trusted certification authority
https://technet.microsoft.com/en-us/library/dd320345(v=ws.10).aspx
Best Regards,
Amy