Hi, I am having a similar issue but only with Google Chrome.
[ATTACH=CONFIG]32515[/ATTACH]
IE 8 the legend shows up fine.
[ATTACH=CONFIG]32514[/ATTACH]
I am hosting the map service from AGS 10.0 SP2 inside of our company firewall as well. (only internal users can view the data)