Colloquially, it's any new business. Average folks will think of a new retail storefront, or new one-man consulting business, as a 'startup' -- and there's no need to disabuse them of that usage, it's reasonable in that context.
In technology circles, it especially connotes a business with extra reward and risk, trying something novel.
In the customer-development/lean-startup formalization of positive startup patterns, Steve Blank defines 'startup' as "an organization formed to search for a repeatable and scalable business model". See:
http://steveblank.com/2010/01/25/whats-a-startup-first-princ...
Are you searching for a repeatable and scalable business model? If so, you're a startup! If you form a partnership or corporation to search with more collaborators, then that formation, too, would be a startup.