For arbitrary bases I think this should do what you want.

factorialZeros[n_Integer, b_Integer] /; n > 1 && b > 1 := 
 Module[{pfacs, pexpons},
  {pfacs, pexpons} = Transpose[FactorInteger[b]];
  Min[Floor[
    Map[Sum[Floor[n/#^j], {j, Floor[Log[#, n]]}] &, pfacs]/pexpons]]
  ]

For example:

In[86]:= factorialZeros[243, 12]

(* Out[86]= 118 *)

Cool post Peter! Numbers with lots of trailing zeroes before the decimal point appear many unexpected places in discrete mathematics and combinatorics, such as the number of possible Rubik's Cube scrambles (43,252,003,274,489,856,000).

As you have shown, it tends to happen for numbers which can be derived as the product of several combinatorics functions (e.g. permutations and combinations) like the number of possible Rubik's cube scrambles, or a number which is a factorial of a very large integer.