"A startup is a human institution designed to create a new product or service under conditions of extreme uncertainty."
Is every new company a startup? No, lots follow templates within fairly known parameters, such as Restaurants. The uncertainty isn't there to the same degree, and the offering is known. They are a new company, but not a startup company.
Is every old company not a startup? No, many have to deal with the innovators dilemma and as their main business face competitions are forced to confront uncertainty and create divisions to reinvent themselves, these divisions would be considered a startup.
Eric defines a startup by the uncertainty factor, and by the creation of a new offering from that uncertainty.
Edit: typo corrected
“… a human institution designed to create new products and services under conditions of extreme uncertainty.”
Assuming most readers know what you meant, but just had to correct it, for the record.
Kindle should really allow cut and paste, a fair use amount (let that debate begin!). Then I wouldn't have got it wrong.
"... a startup is a new business designed for scale ..."
more in context:
The first component is particularly helpful in the first stage of a startup's life, when you go from merely having an interest in starting a company to actually doing it. It's quite a leap to start a startup. It's an unusual thing to do. But in Silicon Valley it seems normal. 
 Starting a company is common, but starting a startup is rare. I've talked about the distinction between the two elsewhere, but essentially a startup is a new business designed for scale. Most new businesses are service businesses and except in rare cases those don't scale.
The actual article: http://www.paulgraham.com/hubs.html
This would filter out all the usual suspects Facebook, Twitter, 37 signals, while keeping Path, Instagram and all the YC funded companies. It would also cut out the new neighborhood bookstore, most service businesses and that sweet home business. Also it would cut out companies that have already reached $1-2bn in valuation (as they cannot realistically grow to become $100bn companies in 5 years).
I get sick of these 10 year old successful companies constantly referring to themselves as startups. That's similar to a thirty year old calling himself a teenager.
Notes on your definition:
You could exclude apple as an outlier by changing "in the next few years" to "in the first few years".
Concerning the significance of growing by a large factor; you might want to consider changing the absolute number to a recurring value. 500 users in the first year which turn into 5000 after five years is hardly significant. 500*5^5 = 1.562.500 is starting to feel significant. The actual growth factor per year might need to be altered.
"repeatedly grow by a large factor (5x or more)"
Ambitions and plans could be refactored to "aims"; if you're aiming to do something you probably have the ambition and you sure as hell need to have some plans or your ambitions won't go anywhere. Although it might be better to explicitly mention ambitions and plans.
In conclusion, my refactored definition would be
"A startup is a business which aims to repeatedly grow by a large factor (5x or more) in the first few (1-5) years.
Personally i think calling very well established businesses like 37signals a startup is quite insulting, as to me, its saying they're not successful, which they clearly are.
I like PG's "make something people want" It describes a successful startup. So successful startups make something that people want that they can scale tremendously. As swombat points out, big companies just can't keep making the magic happen, so by my definition they stop being a startup.
If we go with the TC definition, Facebook is still a startup :)
What I really want to know is what is the difference between "startup" and "small business"?
I think it has more to do with the current state of a company - that is, immature: still figuring out internal roles, processes, possibly no finalized monetization strategy, etc.
Most businesses I come across that describe themselves as startups and fit the rest of the definition, haven't yet got themselves to a point where a 10x improvement over the next year would make them that significant.
However I'd argue with you about Apple. Like you said, Apple didn't hit the time-frame requirement. Wouldn't you also agree that a true startup needs to have the requirements you listed but at the same time start from zero. Companies that just start out, have the growth you talk about in the time frame you talk about would definitely be startups. Companies that have been around for a while and suddenly have explosive growth and hit the other requirements only resemble startups. Google, Apple, and Facebook feel like startups but have certainly grown out of that phase. Being a startup in my opinion a one-time phase that you cannot go through again once you're established no matter how explosive your growth is.
In any case I like your definition and I think it's important that we have one. The word startup is easily overused in an attempt to attain that cool factor some companies have and to ride a trend instead of getting by on the companies real merits.