So this morning, no one on RDS had printers again.

WTF..

So I manually added a printer direclty on the RDS server (not from the Print Server (the DC)). IT showed up immediately on all users and was able to be printed to.

So I manually added all the printers direct. Issues resolved for the moment.

FFS Microsoft...