I occasionally have this problem aswell, although, it seems, not as often as you. It only happens when I boot from cold. To get round this, if it shows up on the first boot I reboot and boot with no startup-sequence, leave it for a minute or two, then reboot. Works everytime.
But, if you are getting this every time you reset, it probably won't work for you.
I've had this problem with 3.5 aswell (although, *very* rarely), and used the same solution
btw, I've got a 68030/40 with 16Mb ram.
