You might first try starting the game from the shortcut that is added to your Programs menu. If it works, just delete the desktop shortcut and copy the Programs shortcut to the desktop. Some Vista / Win7 installs create desktop shortcuts with limited privileges which can cause problems similar to what you describe.
I ran Duke3D on my Vista laptop using the DOSBox and eDuke32 methods, Both ran well but I preferred the eDuke32 (IMHO). Just make sure you install both / individually by right clicking the setup.exe and click "Run as an administrator" on the resulting dialog. If you just double clicked the setup.exe for both / either, you may have a partial install which limits disks read / writes.
I would also suggest you turn UAC off prior to installing, install in a directory outside of Program Files and make sure you right click the game shortcut, click Properties, click the Compatibility tab and check mark "Run this program as an administrator" after the install. After that, if problems persist, try different compatibility modes starting with the newest and working backwards to the oldest.
Edit: Might also check mark "Run in 256 colors" on the shortcut compatibility tab before re-installing etc.