Here are the steps I've found seems to work to avoid this problem:
1. Right Click on HAL Icon in system tray, Select General Options, then go to the Startup Tab. Select "I want HAL to start like a normal program from the start menu..." Click OK.
2. Right Click on the HAL Icon in the system tray again, select "exit HAL".
3. *** IMPORTANT STEP *** Click on Start Menu, go to Programs (Win98) or All Programs (XP), Startup menu. You'll see "Ultra Hal Assistant Startup". Click and Drag it to any other folder (like the Ultra Hal Assistant) in your Start Menu's Programs (or All Programs) folder. This should move this particular file.
*** NOTE: XP users may have to RIGHT CLICK on the start menu, select "Explore All Users" and find it in either the "All Users" or your username Start MenuProgramsStartup as just moving it may (or may not) still cause conflicts depending on where the shortcut was actually located.
4. Reboot. You should no longer get a message about a problem with shutdown.
What's happening is, while the icon in the tray isn't supposed to start, it's still starting because it's in the Startup menu.