It probably has something to do with the startup process then. Maybe somebody knows offhand what this is from previous experience. Have you installed any new programs(etc) that launch on start-up? It'd be harder being a start-up problem, but you could also try watching Activity Monitor for something erratic happening when the error message is up.
P.S. Yeah, and I had a dream about this post. Odd, eh? I was floating through space and a large, bland error message floated in front of my visage...