Buddhism is not the reason, for sure.
Tatami is probably not the reason, either.
I am a Japanese man but I am no expert on this subject, though.
I am simply trying to answer the question based on what I have been taught in primary school in Japan.
The removing shoes has been already a custom during Heian period (794-1185), when importing Chinese culture became less important. You can be sure when you take a look at the picture scrolls of this period (see, for example,
http://www.h6.dion.ne.jp/~chusan55/mukashi2/36mukashi.htm).
The custom became possible because of the structure of the rich people's building known as Shinden Zukuri (see,
http://en.wikipedia.org/wiki/Shinden-zukuri). The layout of the building was modeled after the Chinese aristocratic mansions but the structure of the individual house originated from the Takayuaka-shiki (lit., high-floored) building, which is after high-floored warehouses in Yayoi Period (before 300BC, see eg.,
http://www2.tba.t-com.ne.jp/atelier_O/02-takayuka-jyukyo.html). This is a popolar structure throughout Southeast Asia even today (see, eg.,
http://www.phoenix-c.or.jp/~mtanaka/page678.html). Because this structure is particular to the Southeast Asian culture (vs Northeastern Asian culture), there is an argument to the origin of Japanese people, by the way (see, Wazoku-ron, lit., Wa-People Theory).
Tatami was a very expensive item during Heian period. It was used primarily as the bedding base for the rich people so most of the floors were covered by bare wooden surface. Even when tatami became less expensive commodity in the following periods, the samurais were still sitting on the floors in the simplified Shinden Zukuri (known as Buke-Zukuri, lit., Samurai-Structure), following the Heian customs.
Removing shoes inside a Takayuka-shiki building is a natural consequence as many people have argued even within this thread. I would like to point out, therefore, in addition to the other arguments, that since Takayuka-shiki was originally suitable to the paddy field with periodic flood (basically, muddy field or water beneath the floor), the wooden floor is not made sturdy. You do not want to ruin the floor with your shoes or the weight from the foot of chairs....