I've experienced exactly the same issues with other hardware and it turned out to be fixed with a new BIOS version from the graphics card manufacturer - in that case for my Dell LCD monitor with an ATI Radeon All-In-Wonder card. The problem was that the monitor couldn't cope correctly with what the graphics cards BIOS was telling it to expect the picture as. The reason why it works fine once Windows loads (as it did with my situation just mentioned) is because during the Windows loading process, drivers take over controlling the graphics card from the cards own built in BIOS.
It's definitely an issue you need to raise with the graphics card people (and possibly the monitor people). If either give you a firmware update for their hardware, hopefully the problem will be solved as a result. Note that you may need to be persistant as in my case it took many (around 5 ~ 10?) emails to get an updated BIOS out of ATI. It was a long time ago but I remember initially the level one tech support person said there weren't any BIOS updates for the card and it took persistance to get the matter escallated. In the end they'd only swap the card with one already containing a new BIOS but once I received that card, I managed to find a utility that captured this cards new BIOS to a file so I could then flash my other identical Radeon All-In-Wonder card to also get it working with the same monitor.