I have seen all sorts of problems cropping up with NAV/other programs not interacting well. It seems like the latest versions of NAV are "hogging" everything, making it difficult for other programs to find space to work. I am suspecting that when NAV starts with Windows it loads a dll into the memory space that Nero wants to use.
You didn't say which version of Windows you are running, but one option is if you are running 2k or XP is to set up another user account just for bruning. Keep everything the same in it, except don't add NAV to it. That way you can surf and download under the protected account and then burn without NAV getting in the way.