One key difference is that they are not trained with end-to-end optimization but rather a hand crafted learning rule. This rule has strong inductive biases that work well for small datasets with pre-extracted features, like tabular data.
Their big disadvantage (and this applies to logical/symbolic approaches in general) is that they don't work well with raw data. Even easy datasets like CIFAR10. The world is too messy for perfect logical rules; neural networks are able to capture this complexity, but simpler models struggle to.
statistical
Note that learning is a fundamentally statistical process, so Tsetlin Machines are also statistics based.