Hi Hunterp - Start by confirming it was installed, on your iPhone go to> Watch app>scroll down and view the list of apps installed on the watch, as you know they're listed alphabetically. Betting you'll see it there, which confirms it's installed. Now to find it!
I gotta share when I first looked for this app on my watch, the icon for Walkie Talkie wasn't visible on my watch screen, it had been pushed out of view, below the cluster of icons readily viewable on my watch face. I was able to scroll around the watch face and finally located it. To fix this I went back to the Watch app on the phone, to the preference App Layout, found the Walkie Talkie icon and moved it into location more center on the screen.
Hope this Helps!