Power cycle the TV as well -- you may need to unplug it to do this fully. The HDMI circuits are little computers in their own right, and some HDMI handshake failures can leave the TV's HDMI circuit in a wedged state where it can't respond properly to new attempts to connect. This is not normal of course, but it does happen.
And double check that the HDMI plug is fully inserted straight into the socket at each end. HDMI is only a friction fit, and even just the weight of the cable can be enough to shift the plug the little bit that will make the connection fail. Try the "wiggle test" where you grab the HDMI about 1 inch from the socket, press it gently straight into the socket, and wiggle it slightly. Do this at both ends.