Well I am guessing that I am unable to authenticate.
I have went through the process of linking the two applications. This succeeded, and I see the relationship on both Stash and Bamboo. I have also went through the steps to configure both the Outgoing and Incoming Authentication on both sides (OAuth). I found a previous answer to the exact message I am getting, but their issue was that the system clocks where not synchronized. However, Stash and Bamboo in my case are running on the same machine.
Currently, when I try to create a new plan and have Stash selected as the Repository Host, I get an info box with the following message.
Stash - approval required
Bamboo requires your approval before it can display repositories and branches, and automatically set up authentication.
Login & Approve
Even when click the link and approve on the stash side (don't want to do this because this is a user specific authentication) the problem persists.