I am having this issue as well
I just built a new host and patched it to current patch level
added it to the cluster and tested a vmotion - all good
put it to maintenance mode and built out the teaming on the Cisco switches (redundant 6509)
once that was completed - brought it out of maintenance mode and the error appeared
back to maintenance mode and a reboot of the host
still there when it came back up "network uplink redundancy lost"
I tested the host out and appears all links are working correctly
as above - curious about the error