Hmm, it's difficult to doubt Gandalf. But surely there must still be Elves in Middle-earth who outstrip Treebeard in terms of age. Wasn't Cirdan one of the Elves who originally woke by Lake Cuivienen? And what about Tom? I believe that there is a thread about this somewhere around here ...
As for Treebeard's reference to the trees in the dark hollows that were even older than he, perhaps, like Old Man Willow, they were not able to walk.
Edit: There are a few threads on this. Here are two of them:
Who’s the oldest?
Who’s the oldest? (2)