They say it so often, that I would think that they really mean it--under the seat in front of you or in the luggage bin overhead. I would bring it to the passenger's attention first, by handing it to them, or asking them if you would mind if you put their stuff in the overhead bin, since that is your storage space. If they got huffy, I would probably concede it to them, but let them know that the tradeoff for having the extra space in the bulkhead row, is that you don't get any under-seat storage, and then casually confirm it with the flight attendant the next time s/he goes by, but loud enough to make sure the passenger in front of you hears it.