Abstract: The search for new interactions of neutrinos beyond those of the standard model may help to elucidate the mechanism responsible for neutrino masses. Here, we combine existing accelerator neutrino data with restrictions coming from a recent atmospheric neutrino data analysis in order to lift parameter degeneracies and improve limits on new interactions of muon neutrinos with quarks. In particular, we reconsider the results of the E-815 experiment at Fermilab (NuTeV) in view of a new evaluation of its systematic uncertainties. We find that, although constraints for muon neutrinos are better than those applicable to tau or electron neutrinos, they lie at the few X 10(-2) level, not as strong as previously believed. We briefly discuss prospects for further improvement.