Hi, after a couple of months of research and dealing with MS (not helpful at all) I found the solution, I changed the paper type in the printer properties on the local print server and it fixed the issue. I changed the paper type to "Plain and Recycled" and it started working!
As you know, Universal Print uses your local print server, and the connector connects it to Azure AD, so you need to make all the changes on the local print server side.
Please let me know if this solves your issue.
I opened a ticket with MS, and with all the respect, MS support guys have no idea about Universal Print (not sure about other stuff) at some point I felt like I was the one who was supporting them because I was the one who was explaining to them how this works and how I set this up!