Any algorithmic problem has a time complexity dominated by counting? What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

I am looking for algorithmic problems which involve some sort of
counting and for which the time complexity is greatly influenced by
this underlying counting problem. 

Of course, I am looking for problems which are not counting problems themselves. And it would be greatly appreciated if you could provide documentation for these problems.
This is a followup to Suresh's answer.  As he says, there are lots of construction problems in computational geometry where the complexity of the output is a trivial lower bound on the running time of any algorithm.  For example: planar line arrangements, 3-dimensional Voronoi diagrams, and planar visibility graphs all have combinatorial complexity $\Theta(n^2)$ in the worst case, so any algorithm that constructs those objects trivially requires $\Omega(n^2)$ time in the worst case.  (There are $O(n^2)$-time algorithms for all three of those problems.)

But similar constraints are conjectured to apply to decision problems as well.  For example, given a set of n lines in the plane, how easily can you check whether any three lines pass through a common point?  Well, you could build the arrangement of the lines (the planar graph defined by their intersection points and the segments between them), but that takes $\Theta(n^2)$ time.  One of the main results of my PhD thesis was that within a restricted but natural decision tree model of computation, $\Omega(n^2)$ time is required to detect triple intersections.  Intuitively, we must enumerate all $\binom{n}{2}$ intersection points and look for duplicates.

Similarly, there is a set of numbers where $\Theta(n^2)$ triples of elements sum to zero.  Therefore, any algorithm (modeled by a certain class of decision trees) to test whether a given set contains three elements that sum to zero requires $\Omega(n^2)$ time.  (It's possible to shave off some logs via bit-level parallelism, but whatever.)

Another example, also from my thesis, is Hopcroft's problem: Given $n$ points and $n$ lines in the plane, does any point contain any line.  The worst-case number of point-line incidences is known to be $\Theta(n^{4/3})$.  I proved that in a restricted (but still natural) model of computation, $\Omega(n^{4/3})$ time is required to determine whether there is even one point-line incidence.  Intuitively, we must enumerate all $\Theta(n^{4/3})$ near-incidences and check each one to see whether it's really an incidence.

Formally, these lower bounds are still just conjectures, because they require restricted models of computation, which are specialized to the problem at hand, especially for Hopcroft's problem).  However, proving lower bounds for these problems in the RAM model is likely just as hard as any other lower-bound problem (ie, we have no clue) — see the SODA 2010 paper by Patrascu and Williams relating generalizations of 3SUM to the exponential time hypothesis.