Topological phases of matter that depend for their existence on interactions are fundamentally interesting and potentially useful as platforms for future quantum computers. Despite the multitude of theoretical proposals the only interaction-enabled topological phase experimentally observed is the fractional quantum Hall liquid. To help identify other systems that can give rise to such phases we present in this work a detailed study of the effect of interactions on Majorana zero modes bound to vortices in a superconducting surface of a 3D topological insulator. This system is of interest because, as was recently pointed out, it can be tuned into the regime of strong interactions. We start with a 0D system suggesting an experimental realization of the interaction-induced $mathbb{Z}_8$ ground state periodicity previously discussed by Fidkowski and Kitaev. We argue that the periodicity is experimentally observable using a tunnel probe. We then focus on interaction-enabled crystalline topological phases that can be built with the Majoranas in a vortex lattice in higher dimensions. In 1D we identify an interesting exactly solvable model which is related to a previously discussed one that exhibits an interaction-enabled topological phase. We study these models using analytical techniques, exact numerical diagonalization (ED) and density matrix renormalization group (DMRG). Our results confirm the existence of the interaction-enabled topological phase and clarify the nature of the quantum phase transition that leads to it. We finish with a discussion of models in dimensions 2 and 3 that produce similar interaction-enabled topological phases.