As far as I'm aware, the identities provided by the "New Identity" button is only towards clearnet browsing (exit nodes). Connecting to a hidden service doesn't include exit nodes. However clicking "New Identity" might create a whole new tor circuit thus solving the problem. But I agree, restarting the browser will most certainly establish a new circuit.