I have quite a similar situation on one my Fedora installations (Fedora 8 in particular). The system is usually running all the time, so my easy hacking solution was to disable cups and sendmail during startup. When the system is up and running I launch these services by hand, when needed.
Sometimes I noticed on temporarily test installations that mostly at sendmail, sometimes also at cups the booting process hangs. If it takes too long, I do a reboot, and the next time it usually proceeds faster or hangs with the other service. I assume that some network-related environment parsing is done by these tools with multiple probings until timeout limits are reached - but I didn't spend much time to hunt down the problem, so it's only a guess.
Debian