Since I wasn't yet reading Mathoverflow at the time, I didn't see this question until Brian e-mailed it to me in January. I was eventually able to give a more elementary proof by applying formulas of Vélu to the $n$-isogeny from a curve with $j=0$ to one with $j=j(n\zeta)$, which in fact determined $j(n\zeta) \bmod 3^{9/2}$. With some more work I then proved a congruence $\bmod 3^5$ in the case $n \equiv -1 \bmod 3$, and even obtained some information $\bmod 3^6$ for $n \equiv +1 \bmod 3$. Namely:
@ if $n \equiv -1 \bmod 3$ then $j(n\zeta) \equiv -54 \bmod 3^5$; and
@ if $n \equiv 1 \bmod 3$ then $j(n\zeta)$ has valuation at least $9/2$ at $3$, and every conjugate is congruent to either $0$ or $\pm 324 \sqrt{3} \bmod 3^6$.
Brian soon replied that he can understand these refined congruences using the same "Grothendieck-Messing crystalline Dieudonné theory" that he applied to get the congruences $\bmod 3^4$.
Here's a link to a talk I gave here in mid-February that recounts this story and outlines the proofs and some additional information: http://www.math.harvard.edu/~elkies/j3.pdf
