Fortunately I was able to find a solution.
I googled the issue and didn't really come up with much until I remembered DFS - A feature that can automatically detect if a device is interfering with another use such as weather radar and switch off the device. DFS is mandatory on certain 5Ghz channels but not all of them. Some manufacturers either don't implement DFS or get the device certified to use it (I'm not sure which ) which means they can only use 5Ghz channels that don't require DFS.
So I checked which channel my Unifi AP was using and compared it to this 5Ghz Channel Wiki Page and sure enough it was on Channel 56 - a channel that requires DFS. Instead I forced the AP to use Channel 46, a channel that doesn't require DFS, and sure enough the Fire Stick connected instantly.
Anyway.... not the most interesting blog post, but as I struggled to get any assistance from a Google Search I thought I'd throw it up there in case someone else has the same issue.