I would take a look at at post hfr03 hotfix PSE450R03W2K3016 -
http://support.citrix.com/article/CTX119086:
Autocreated printers might fail to fully initialize in the session, causing a "The printer is not installed" error message to appear.
While you may or may not be getting the error message, it sounds like your issue - your printers don't seem to be auto creating correctly.
Another step to try assuming you have roaming user profiles - try rebuilding a test user's tsprofile and let it recreate at next login and see if that fixes it.