Was Old Man Willow a fallen Ent or a different type of Ent? This assumes that the Ents have different species or races much like the elves do.
It's not clear exactly where Willow falls on the continuum of tree-like creatures, but Treebeard implies that he's something at least sort of like an Ent:
Most of the trees are just trees, of course; but many are half awake. Some are quite wide awake, and a few are, well, ah, well getting Entish. That is going on all the time.
'When that happens to a tree, you find that some have bad hearts. Nothing to do with their wood: I do not mean that. Why, I knew some good old willows down the Entwash, gone long ago, alas! They were quite hollow, indeed they were falling all to pieces, but as quiet and sweet-spoken as a young leaf. And then there are some trees in the valleys under the mountains, sound as a bell, and bad right through. That sort of thing seems to spread. There used to be some very dangerous parts in this country. There are still some very black patches.'
'Like the Old Forest away to the north, do you mean?' asked Merry.
'Aye, aye. something like, but much worse. I do not doubt there is some shadow of the Great Darkness lying there still away north; and bad memories are handed down.
The Two Towers Book III Chapter 4: "Treebeard"
This is of course not very helpful, and most people would have guessed this already, but it's all we have from the published canon.
Going back in time a bit, an early draft of the Bombadil chapter says that Willow was an angry spirit that got trapped in a tree:
Amongst [Bombadil's] talk there was here and there much said of Old Man Willow, and Merry learned enough to content him (more than enough, for it was not comfortable lore), though not enough for him to understand how that grey thirsty earth-bound spirit had become imprisoned in the greatest Willow of the Forest. The tree did not die, though its heart went rotten, while the malice of the Old Man drew power out of earth and water, and spread like a net, like fine root-threads in the ground, and invisible twig-fingers in the air, till it had infected or subjugated nearly all the trees on both sides of the valley.
History of Middle-earth VI The Return of the Shadow Part 1: "The First Phase" Chapter VI:"Tom Bomabdil"
I'm not entirely sure of the dating of this passage, but I tentatively want to place it around 1938 - so a very early draft indeed, so how canon you consider it is a matter of personal taste.
This passage suggests that Willow was originally an ordinary tree, but that an angry "earth-bound" spirit got bound up inside of it, and spread its malice over the whole forest. The phrase "earth-bound" is interesting, because it precludes the possibility of him being a Maia; it takes a lot of effort to make one of the Ainur bound to the Earth, as Morgoth found out to his detriment.
Two more likely explanations would be:
- It's a rogue, unhoused Elf soul
- It's a primordial spirit of some other kind; as Darth Melkor (user8719) points out, not all spiritual beings are necessarily Maiar
But this is nothing more than speculation, and again depends on how "canon" you consider Tolkien's early drafts.