An ultra-relativistic particle is any particle you observe to have almost all its energy stored in the form of momentum. In other words, we are talking about particles that have only a very tiny fraction of their total energy stored in (rest)mass.
The relativistic mass-energy-momentum relationship
$$E^2 - c^2 \ p^2 \ = \ c^4 \ m^2 $$
is valid for a particle with (rest)mass $m$ regardless its speed. Depending on the relative magnitude of the various terms a particle is referred to as ultra-relativistic, relativistic, or non-relativistic.
An ultra-relativistic particle speeds by with $E \approx c \ p >> m \ c^2$. Examples are neutrinos (at almost any energy), but also protons accelerated to full speed in the LHC.
In contrast, non-relativistic particles (I prefer to reserve the term classical particles for particles behaving in 'non-quantum' fashion) are characterized by $E \approx m \ c^2 >> c \ p$.
Depending on the relative sizes of the $mc^2$ and the $pc$ sides of this right triangle, a particle is called non-relativistic, relativistic, or ultra-relativistic.