The spectral type of an object is almost entirely determined by the temperature of its photosphere. ie Saying something is type M3.5 is just a measure of its surface temperature. An M3.5 brown dwarf is at a very similar temperature to an M3.5 star.
Brown dwarfs begin their lives as hot balls of gas and gradually cool with time. They start off as M-type objects and then cool to become L-type and then eventually, T-type objects. Stars on the other hand, start their lives by cooling, but stabilise their temperatures at a mass-dependent value that corresponds to an M-type classification or even as cool as type L2 for the very lowest mass stars.
Given that stars and brown dwarfs appear to have been born throughout Galactic history, then a range of masses are possible for any spectral type. In order to use the surface temperature (or spectral type) as an indicator of whether something is a brown dwarf, then you also need to know its age. In general that is not known, unless the object can be demonstrated to be part of a cluster of stars (of known age).
In order to be a brown dwarf the mass should be below about $0.075 M_{\odot}$, but unless the object is in a binary system, this cannot be measured. So what people do is trust the models(!) and compare the luminosity (or estimated temperature) with model evolutionary tracks at a given age. This gives an age- and model-dependent mass that can be used to claim that an object is a brown dwarf.
The fact that brown dwarfs can have an M-type spectral class when they are young, but then move through L- to T-dwarfs as they get older is not a problem, it is a confirmation that the evolutionary models are (roughly) correct!
A plot might help (from the work of Burrows et al. (1997)). This shows the evolution of temperature with time. Each track represents a brown dwarf of a given mass (the tracks from top to bottom) are masses of 0.2 - 0.08$M_{\odot}$, representing stars (in blue). Then come masses of 0.07 to 0.015$M_{\odot}$ representing brown dwarfs (in green, that will never ignite hydrogen in their cores to any extent). Then below this are the "planetary mass objects" from 14 Jupiter masses to 0.3 Jupiter masses at the very bottom (in blue - the definition here is that these objects don't even ignite deuterium in their cores).
The horizontal lines mark the boundaries of the spectral type classifications (M at the top, L in the middle, T at the bottom).
Notice how the stars level-off in temperature (when they begin H-burning) but can have M-type or even L-type classifications, but the brown dwarfs cool throughout their lives. Even objects as low as $0.01M_{\odot}$ begin their lives as "M-type" objects.
To answer some of your more specific queries:
The warmest spectral type below which you can almost guarantee that an object is a brown dwarf is $\sim$ L2. Any object warmer than this could be a star.
A brown dwarf is always cooler than a low-mass star of the same age.
Current observational estimates are that there is about 1 brown dwarf for every 4 low-mass stars - the weighted mean ratio for stars between 0.08 and 1 solar mass to brown dwarfs from observations of several clusters is $4.3 \pm 1.9$, according to Andersen et al. (2008); the commonly adopted/assumed "Chabrier Initial Mass Function" has 4.9 stars for every brown dwarf.
The spectrum of a brown dwarf and an M-dwarf star at the same temperature are very difficult to distinguish. The M-dwarf is only slightly bigger and this might lead to small gravity-dependent differences. Lithium is not burned in brown dwarfs less than $0.06 M_{\odot}$, whereas it is burned completely in low-mass stars on a mass-dependent timescale. Thus an older (than say 1 billion years) M-dwarf star would certainly have burned its lithum, whereas a younger M-type brown dwarf of lower mass would still have lithium.
