I had a flight once in, oh, around 1980 or so when I actually thought that I was supposed to put stuff under my seat. Kind of like I did in school with those little basket/shelf thingys under the seat.
Now I know better and I try to avoid bulkhead seats for this very reason. I often have a very small carry-on, smaller than many purses, just to keep my books, mp3, junk food, Sudoku book and a few other small items. In the rare instances when i am in a bulkhead seat i will ask the person behind me if I could keep it in their space during takoff and landing and show how small it is. So far no one has minded. I think the key here is that I ask first.