For what is may be worth (I'm sure there is a text-message abbreviation for this):
The variant forms that I'm aware of are Narbada and Nerbudda (the latter probably just a British rendition of the former). As for the change of m to v (actually, β), what's involved is more complexed -- a lenition of m (which, as the Sanskrit phoneticians already realized, is a voiced labial *stop* with nasal coarticulation) yields in the first place a nasalized voiced labial fricative or approximant (something whose correct phonetic representation may not survive crossing the ether, computer systems, or platforms). This, in turn tends to "lose" its nasalization to a neighboring vowel, as in Hindi गाँव, which in yet a further turn will be denasalized in Modern Marathi. This means that in principle one could go from m to v/β, but it would be a rather tortuous route. What creates problems is that this lenition of m only takes place intervocalically, not in clusters. So, the only way one could get lenition to apply here is by assuming that the earlier name was something like Naramada. This could, of course, be nicely etymologized in Sanskrit -- but is it attested anywhere in Sanskrit? A further problem is that the change v/β > b normally is limited to initial position. A way around that would be to assume something like this scenario naramada > nara˜β/ṽada > nar˜β/ṽada (with syncope of the second vowel) > narβ/vada > narbada, with change of v/β to b after consonant (I'm not sure there are examples for this from Indian languages, but the change is found elsewhere). However, if you run the word through this "Prakritic" changes, you need to worry about the d of narmada -- why did this not undergo lenition, too, winding up as Ø, hence unattested narmā*.
A less convoluted account would consider the b of Narbada/Nerbudda to be the result of nasal dissimilation in the sequence n … m. A change of this type is found in asmin > Pkt. a(p)phe etc., with sm … n > sp … n (v. Hinüber Älteres Mittelindoarisch).
Cheers,
Hans Henrich Hock