Palm didn't have 6+ years of iPod / iTunes profits to plow into R&D. And Blackberry's core customer didn't yet know they were interested in something like an iPhone: a mobile Bloomberg terminal was the apple of their eye.
I think we're in agreement while disagreeing. My fascination isn't so much that the phone companies couldn't do it (because they could), but that they didn't (because they couldn't even imagine it).
Props to Twitter for envisioning the product, but "What if?" phone companies had {Twitter, Facebook} is an entirely plausible, albeit organizationally-unlikely present.
It would have required them to pivot their thinking from maximally taxing use of capital-intensive investments to growing scalable platforms, but stranger things have happened. And the internet's growth was already obvious in that time frame.