I think you would be better off using CDRs to start with, instead of CDRWs, but if you can, try a couple of different brands of CDR just in case.
You're right, it could be the software thats the problem, if you have access to any other CD Writing software then I would trying installing that instead. The problem could also be the blank CDRs themselves or the actual CDRW drive, as you suggested.
Before you do anything though, just check these things :
1. Make sure that you have disabled as many of the programs that run in the background as possible (e.g the icons that appear in the system tray next to the clock)
2. Make sure you're not running any other applications at the time e.g internet explorer etc
3. I assume you are transferring the photos from camera to hard drive first before burning, right? Make sure you have plenty free disk space & defrag the hard drive
4. If the software you are currently using gives you any option to do so, then try letting it create an image file first instead of burning the photos to CD on the fly.
5. Also try lowering the burning speed (depending on the speed of yur computer, try 4x or 8x)
6. Try disabling power management as well in windows.