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...