View > Theme is a red-herring. Ignore it.
Go to TextMate > Preferences and choose Bundles. Themes are in bundles in TextMate 2. In the Bundles tab, you can click themes near the top to filter theme-bundles.
Choose the bundle called Themes. When you check the box, it will download and install. Quit, relaunch and you're done.