You really shouldn't have to enter all muxes, one should be enough as long your provider supplies a NIT (Network Information Table) and you have network discovery enabled.
Tvheadend should then find the rest by itself but obviously this isn't working which makes me think that not all (if any) muxes are in the NIT.
You've already ruled out the tuner is at fault, so I suspect you're entering the wrong information into some fields.
If you're using DVB-T (and I assume you are) make sure that you're entering the correct number of zeros in the frequency field, I'm not sure whether w_scan gives 6 digit frequencies or not, but I know (here in the UK at least) you need to enter 9 digits.
e.g, for frequency: 522000 (UHF channel 27) you'd need to add three extra zeros when entering into Tvheadend. (522000000)
Additionally (and depending on your tuner) you may need to supply more frequency information instead of using just AUTO but usually you'll get away with just supplying the frequency and bandwidth, the tuner will more than likely figure out the rest.
HTH