Q: What does it mean that I have a very long (10 min.) boot sequence with many "queue overflow" messages?

The boot process (which takes approx 10 minutes) displays a lot of messages like:

overflow
ncr53c895-2:15: SIR 18, CCB done queue
overflow
...
ncr53c895-2-<13,0>: QUEUE FULL! 0 busy, 22 disconnected
CCBs - max tags set to 23

Eventually the process completes and the disks seem to be available. Are these messages normal, or do they indicate a problem?

A: Only from a performance viewpoint. You are maxing out the SCSI bus, and processes are having to wait for I/O access. You might want to look into load balancing and/or upgrading.