« Qu'à cela ne tienne » est une locution proverbiale figée.
Il n'est donc pas possible1 d'en modifier le temps ou quoi que ce soit, ce qui ne pose d'ailleurs aucun problème dans les textes envisagés :
Ils ne trouvèrent pas de restaurant. Qu'à cela ne tienne ! Ils se mangèrent entre eux [sic].
Ils n'avaient pas trouvé de discothèque. Qu'à cela ne tienne ! Ils avaient chanté eux-mêmes.
Voici un exemple d'utilisation de cette locution dans une phrase à l'imparfait par Jacques Savoie, Un train de glace, chap. 3, p 45:

1 Vous démontrez le contraire puisque Chateaubriand l'a fait.
Dans l'expression « Je lui répondis qu’à cela ne tenait », il ne s'agit plus tout à fait de la locution mais de sa retranscription, la phrase originale étant :
Je lui répondis « – Qu'à cela ne tienne ! »
Comme on aurait pu écrire
Je lui répondis qu'à quelque chose malheur était bon
pour
Je lui répondis « – À quelque chose malheur est bon »
La concordance des temps s'impose alors sur le reste.