A startup is a company that creates wealth rapidly by creating technology a lot of people need. While I don't know the details of 37signals' finances, it seems likely that they'd count as one by my definition.
I think the thing that makes people think 37signals is not a startup is that they currently seem to have no interest in selling the company, but instead pay themselves a lot of the revenues as dividends. That's a matter of personal preference, but as I explained here,
they amount to the same thing.