If it still does not show up, try the MrMC app as a workaround. It has an integrated Plex client.
The Lite (free) version has some limitations (see MrMC Forum post). The paid version is $2.99 USD.
FYI, there is a compatibility problem with the Plex app and the Toshiba Fire TV Edition sets. Hopefully you’re not seeing the same thing. More information is available in this post.
