I think I have answered my own question, but as I couldn't find it documented anywhere I thought I'd post for future reference. (feel free to point me to where it is documented if I am wrong)
It appears that if you do not enable "web access" for your map service the legend widget fails. Looking at the Chrome diagnostic, the actual image URL seems to be
Which seems to confirm what I discovered after a lot of grief, no web access, no legend.
ACM
Edit- Doh! IT is documented, I just didn't fully understand it.
If the layers are version 10 or lower the legend is created using the ArcGIS.com legend service. In order to use the ArcGIS.com legend service your map service needs to be publicly accessible and your application must be able to access ArcGIS.com.
