I think a "startup" is an innovative company that has existed for a short period of time. If it's software, it's probably still in beta. A startup is probably in early research and development stages. A startup is probably looking for some outside funding and the founders have some exit strategy in mind (Acquisition or IPO).
A pillow store is none of the above things so it's most probably not considered a startup. A game development shop can be a startup if it meets some or all of these things. Web development firms can be startups when they make web applications for the public or businesses to use (like 37signals).
Just my 2 cents.
All companies exist in volatile markets regardless of whether its a mature (many competitors) or new market (must generate demand for product). They all need to differentiate themselves from their competitors in some way in order to be successful, so all companies will have to innovate some aspect of their business.