Labial > velar and vice-versa are pretty common changes, esp. in the Americas.  Off the top of my head, I can list these:

p > k universally in Arapaho

kw > p/pw/bw/v in Nahuatl

f > x/h in some Salish languages

xw > f/fw in Halkomelem

m > N (as part of a larger strategy of de-labialization; I can't recall the specific language, but it traditionally didn't have labials, but acquired them from loan-words--and then quickly backed them, mostly to velar, and to palatals before front vowels)

There seems to be some close articulatory association between the labial and velar POAs, such that one can easily become the other without any obvious phonetic motivation (esp. labial>velar; the reverse does occur, but is less common).  Labials can become dentals/alveolars, but this is rare compared to labial > velar, and is usually conditioned by vowels or consonants (like ps > ts, or sp > st).