Apple's online store now reflects a new expected shipping date for new Apple TV orders:

Early U.S. Apple Store orders still show a March 20th ship date. Australian orders have been moved back to March 27th.
Meanwhile, Apple stores have started getting inventory in, but are unable to post materials until at least Wednesday.
Update: Customers are reporting they have received shipping notices.