Is the "upper labial frenulum" (the weird piece of skin between your
top lip and gum) evident in all primates and if so, does its evolution
demonstrate a need for more elaborate language and communication as
man adapted?

Hi there!

What a fascinating question!

According to a page of Primate Definitions, it appears that the upper
labial frenulum (or "lip frenulum") is not present in all primates. 
From the page:

"frenulum: "small fold of skin immobilizing the upper lip; present in
all extant strepsirhines but reduced or absent in extant haplorhines."
[http://members.tripod.com/cacajao/evolution_definitions.html#f]

So what's a strepsirhine, you ask?  "Primitive" primates, such as
lemurs and lorises.(My apologies for the super long URL)
[http://216.239.39.100/search?q=cache:gf092HkAgo0C:www.anthro.ucdavis.edu/courses/f00/ant154a/outlines.PDF+strepsirhines&hl=en]

And haplorhines?  Primates such as apes, chimpanzees and humans.
[http://ijolite.geology.uiuc.edu/00SummerClass/geo143/lectures/lect13B.html]

Apparently, that little bit of frenulum we humans have is considered
"reduced", and has thus not evolved with us so much as disappeared as
we have evolved, leaving us with that curious bit of skin and no idea
why we have it.

Dr. Alan Greene says that the purpose of the frenulum is to guide the
development of the mouth during early gestation.  What remains helps
guide development of baby teeth, and eventually recedes.
[http://www.drgreene.com/21_93.html]

In humans, overdeveloped frenula can interfere with nursing/suckling,
and can cause speech impediments later.  It is common to snip the
labial frenulum in children with impaired sucking ability or speech
impediments - the higher up on the gum the frenulum is, the more
flexible the upper lip will be.  A good example of this can be found
through LaLeche League:
[http://www.lalecheleague.org/NB/NBSepOct00p161.html]

It would appear that, rather than being necessary for advanced speech,
the upper labial frenulum is actually a hindrance.

Search terms used included "labial frenulum" primates
                           "labial frenulum" speech
                             strepsirhines
                             haplorhines

Hope this answers your question!  Thanks for such an interesting
thought!

great work. easy to understand, and lots o' useful links.