In Erlang, the most common data structure is the linked list. There's no way to search them other than linearly. You are claiming that in general we should suspect that Erlang programmers are incompetent?
In the case of sharding by project, it actually seems like a decent move given that a single Basecamp account has potentially large space requirements (75 GB), and you can't realistically provision enough space on a box to meet all the needs of a bunch of expanding accounts on that box. Being able to throw an entire project onto a new server and assuming that everything associated with a project is on that one server are both nice simplifying assumptions which seem like they would strike a nice balance.
Please stop painting everything with broad black and white strokes, programming and business in general are frequently more about striking the right balance of compromises than about knowing the "best" way to do things. There's usually not a universal "best". 37Signals seem to be doing a marvelous job balancing those compromises between their various disciplines, especially given their massive success with customers.
Edit: This is assuming they're storing attachment files on the same machine, which might very well be wrong. It would be pretty hard for one group to get up to 75GB of todo's and other text content...
While I fully agree that trade offs like yours do occur in our profession, their mere existence is no argument against my initial non-trust of 37signals' competence: you need to actually demonstrate that this problem is one of those cases, and I think that would be difficult to do.
The problem of associating entities in a way that their associations can be modified easily and consistently (i.e., normalization) is effectively a solved problem. Just like the programmer complaining that his program is slow because he's doing a linear search through a linked list, a BaseCamp programmer complain that a requested feature is difficult to implement because their data is in an abnormal form does not inspire confidence, and certainly gives no reason to trust his competence.