There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.
The reason for this is that we expect any factoring-type algorithm that works over the integers, to also work over other number fields (ignoring for now the issue of unique factorisation, which in principle can be understood using class field theory). Thus, for instance, we should also be able to count the number of prime factors over the Gaussian integers, which would eventually reveal how many of the (rational) prime factors of the original number n were equal to 1 mod 4 or to 3 mod 4.
Using more and more number fields (but one should only need polylog(n) such fields) and using various reciprocity relations, one would get more and more congruence relations on the various prime factors, and pretty soon one should be able to use the Chinese remainder theorem to pin down the prime factors completely.
More generally, the moment one has a way of extracting even one non-trivial useful bit of information about the factors of a number, it is likely that one can vary this procedure over various number fields (or by changing other parameters, e.g. twisting everything by a Dirichlet character) and soon extract out enough bits of information to pin down the factors completely. The hard part is to first get that one useful bit...
[EDIT: The above principle seems to have one exception, namely the parity bit of various number-theoretic functions. For instance, in the (now stalled) Polymath4 project to find primes, we found a quick way to compute the parity of the prime counting function $\pi(x)$, but it has proven stubbornly difficult to perturb this parity bit computation to find other useful pieces of information about this prime counting function.]
If N is a prime power it is of the form $p^i$ where $i \leq \log_2(N)$. One can thus compute each of the first $\log_2(N)$ roots of $N$, and test if the resulting number is (first an integer) and then if it is a prime using the AKS algorithm (although perhaps Shor meant to use a randomized test, such as Miller–Rabin, as the paper pre-dates AKS). Obviously if $N$ is a prime power this will produce the factorization.
Best Answer
For semiprimes, computing the Euler totient function is equivalent to factoring. Indeed, if n = pq for distinct primes p and q, then φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = (n+1) - (p+q). Therefore, if you can compute φ(n), then you can compute p+q. However, it's then easy to solve for p and q because you know their sum and product (it's just a quadratic equation).
If you believe factoring is hard for semi-primes, then so is computing the Euler totient function.
Update! Factoring and computing the Euler totient function are known to be equivalent for arbitrary numbers, not just semiprimes. One reference is "Riemann's hypothesis and tests for primality" by Gary L. Miller. There, the equivalence is deterministic, but assumes a version of the Riemann hypothesis. See also section 10.4 of "A computational introduction to number theory and algebra" by Victor Shoup for a proof of probabilistic equivalence.