Try a different optical drive, if possible.
You could try rebooting into safe mode (hold down the F5 key while Windows is starting), and see if the game will start with a minimum of background programs running. That may not help, though, since disabling NAV should be good enough to avoid conflicts, and it sounds like you have shut down all other non-essential programs.
The beta version of Windows XP SP2 has a problem with Starforce copy protection, though the release version does not.
If nothing else helps, in the error message, click the 'Information' button, then when that finishes, click the 'View Report' button. Save the resulting text file somewhere, optionally zip it, and email it to Larian (support@larian.com) with a description of the problem. They can create a file the copy protection can use to check your system on startup, rather then the play CD.
