Hard to tell if you had a lax flight attendant or if the aircraft allowed it without knowing the specific type, but the 767 (which could fit the description above) is the only one with a big enough foot cubby for stowage - can't recall if it's placarded "no stowage" or not though. Honestly overhead space is never an issue in the premium cabin I always put everything up for takeoff/landing.