Easy problems with hard counting versions
One interesting example from number theory is expressing a positive integer as a sum of four squares.  This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution.  But counting the number of such representations would allow you to compute the sum-of-divisors function $\sigma(n)$, which is random polynomial-time equivalent to factoring $n$. So the counting problem is probably hard.