The host that this was happening on was version 5.0 and had several days of uptime. I suspected the host. I moved the VM to a 5.5 host (that we were migrating to anyways) and the storage vMotion was able to be carried out without problems.
Googling I found that the related KB is 1003734 . Reading it, you find a lot of troubleshooting information for compute, or host-to-host vMotion, but not as much for storage vMotions. I did find this though:
I believe that this may be the problem. I am not sure why I can browse the datastores ok, but since moving it from one host to another solves it, I assume either some service has failed on this long running host on a soon to be unsupported version, or there is indeed a SAN zoning problem.
Hope it helps someone!