R - 148 chars
(so far away from the rest of the competition but still)
f=function(n){ q=rep(n,n) r=c() for(i in 4:n){ while(q[i]){ r[i]=paste0(q[i]%%i,r[i]) q[i]=q[i]%/%i } } which.max(sapply(lapply(strsplit(r,''),`==`,4),sum)) } Basically transform the input from base 10 to all bases from 4 to n (using modulo %% and integer division %/%) and pick the index of the one with the most 4s.
f(624) [1] 5 f(444) [1] 10