Hi Mike,
Is this pure IPsec tunnel or GRE over IPsec tunnel?
Can you ping those printers from AIX server when problem of print queues happens? If you are able to ping those printers then it could be a fragmentation issue due to IPsec tunnel.
What are the VPN end devices ? PIX or routers ?
Try to adjust TCP MSS vlue to 1300 and then check if the problem still happens .
Try to adjust TCP MSS value on PIX if your vpn end device is PIX .
sysopt connection tcp-mss MSS_size_in_bytes
example : sysopt connection tcp-mss 1300
You can also find the exact size for your connection using extended ping utility from your workstation as explained in following link .
For PIX and router( as vpn end devices) use following link
http://www.cisco.com/en/US/products/ps6120/products_configuration_example09186a008081e621.shtml#Issues
HTH
Saju
Pls rate if it helps