On a recent flight on CO, I was unable to check in online - alas, I figured that I had the dreaded quad-S... but upon checking in at EWR, the agent simply looked at my ID, entered some information off of it and headed me a "clean" boarding pass.

Upon my return, I was unable to check in at the kiosk. This time, the agent was a little more confused and a supervisor of some sort came over and said "oh - he's a no fly... pull up the record, see this person was born in XX year and he was born later than that so enter this code and put a copy of the record in my in box."

Anyone heard of this before? Does this mean that someone that shares my name can't fly and I'll be paying the price by having to talk to an agent every time I fly?

Probably...could be that someone that shares your name lost his/her passport or some other important document. That name gets added to the list.