Toothpaste is what is called a non-newtonian fluid, more specifically toothpaste is a Bingham plastic. This means that the viscosity of the fluid is linearly dependent on the shear stress, but with an offset called the yield stress (see figure below). This yield stress is what makes it hard to say whether it is liquid or solid. The fact that toothpaste is viscous alone is not sufficient to explain this, because water is also viscous, but doesn't behave like a solid (unless frozen, but that's another phenomenon).
What the yield stress does is the following. Below a certain shear threshold the fluid responds as if it where a solid, as you can see happening when you have put toothpaste on your toothbrush, it just sits there without flowing away. A highly viscous but newtonian fluid would flow away (although slowly as pointed out by @ron in his comment to the answer of @freddy).
Now if you put sufficient shear stress on the toothpaste, when you squeeze the tube of paste, it will start flowing and respond as a liquid.
Other examples, as mentioned in the wiki link in my first sentence, are e.g. mayonnaise and mustard. Another example is silly putty.