"Then it sits there for about 15 seconds (nothing is typeable) and finally I get the modem message and it shuts down fine.
Any ideas what's causing it?"
That is normal as linux is shutting down processes,daemons,services. Same thing happens in windows. They just slap a Pic up instead of showing you the shutdown process. You can see Windows startup same with hitting f8 and boot with command line mode will show drivers and services being loaded,etc...
Older Linux screens showed these processes on bootup and shutdown by default.