I flashed my new Fire today running 5.1.1 with CM12-1 and GApps without issue.
cm-12.1-20160311-UNOFFICIAL-ford
open_gapps-arm-5.1-micro-20160320
Using the flashfire app that comes with superTool. I used the tool to do a wipe and than install of the 3 zips (the 3rd zip is for superUser).