I work at a medium sized business and we're having little trouble adopting Trello. It's been about 8 months since we started, and other departments have also adopted it for their own projects. Once introduced, they love it. It's a great way for everybody within the company to have visibility of what others are doing.
We meet regularly with other departments to triage their request queue (list) and move it forward. It's great for them to see the software process and see their request in context with the (many) other requests.
We often break out separate project boards and link to it from a master (planning) board. That really helps break down the larger tasks.
mhp noted that it's not designed for bugs, but we have no problem using it for that, in conjunction with some GitHub issue tracking.
I'm certain a startup would have no issues adopting it into a great workflow.