Same problem with debian unstable, Ubuntu jaunty, both ship zsh 4.3.9. I know of multiple people with different configurations.
After reading http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=514152 I added
zstyle ':completion:*' special-dirs true
to my config and now everything works fine again.