Scott,
I opened a support incident with Microsoft, and one of the guys there figured out the problem.
Apparently the issue only happens in Windows 7, ON PURPOSE!
This probably explains why no one else was seeing the problem.
The fix is to MANUALL add a DWORD key to the registry.
Here are some links…
http://support.microsoft.com/kb/2011767
http://news.softpedia.com/news/Windows-7-RTM-Can-t-Print-Large-Page-Documents-130269.shtml
A very frustrating problem whose 15 minutes of fame has thankfully come to an end.