Triangle to Quad produces disconnected triangles
From that exact view (all those exact faces selected): 


Hit X, then faces to delete the mess you have.
In edge mode,Alt+Right Click an edge, to select the loop around the hole.
Hit F to fill with an ngon.
Then hit Ctrl+T to Triangulate. 
Then hit Alt+J to do a Triangle to Quad


EDIT: 

Mr Zak's suggestion to use Grid Fill greatly improves this answer by reducing the last three steps to just one:


Hit X, then faces to delete the mess you have.
In edge mode,Alt+Right Click an edge, to select the loop around the hole.
Hit Ctrl+F then Grid Fill