Old Basque is often analysed with 9 consonants : /p t l r k s z n h/ I believe. A counterexample to the /p n/ implies /m/ rule. The modern reflexes of all stops are voiced unless doubled, so one could propose they were voiced in Old Basque as well. (The Trask Basque dictionary does this, and even leaves out /h/, setting it to 8 consonants, but says /h/ existed as a suprasegmental feature.)
Didn't Old Basque have /b/ but not /p/? (/p/ but not /p:/, w/e)
Probably, but I dont really like analzying the fortis consonants as separate phonemes. There are only a few words where there is a contrast like /alda/ vs /alta/, where one might be reluctant to say that the fortis stops are simply geminate forms of the lenis stops, but there are some languages, such as Finnish, where clusters like /ltt/ can be found, so I dont see it as a conflict.
But I suppose you were posting that to say that it doesn't violate /p n/ --> /m/, rather than that it should have 15 consonants instead of 9. Sorry. Still, it bothers me to conceive of a language where all the stops are voiced by default and all the fricatives are voiceless by default, since stops are less sonorous. The fact that so many proto-languages have bizarre phonologies makes me wonder if it's simply impossible for us to reconstruct that far back, and that instead of making protolangs with bizarre phonologies that develop into modern languages using common sound changes, we should focus on protolangs with unremarkable phonologies that transform into modern langs using bizarre sound changes.