What the FAA says is that all airlines are to set their own regulations and these regulations have to be approved by the FAA before taking effect so in a way the FAA is responsible for what restrictions the customers are given.

Here's a link that explains the procedure.
http://www.faa.gov/apa/pr/july/july_22.html

or
http://www.faa.gov/avr/afs/atos/docs...i/s3_1_5op.pdf
http://www.faa.gov/avr/afs/atos/docs...T2R0rg-Ops.pdf

(you need acrobat reader with the last 2).

So technically the carrier is right because their regulations are approved and then enforced by FAA.