@doniks I finally got it working! I had to use the -w flag when doing the fastboot commands.
The full steps I used for the successful flash:
ubuntu-device-flash touch --channel=ubuntu-touch/stable/ubuntu --device=flo --bootstrap
# Reboot into bootloader
fastboot flash -w boot boot.img
fastboot flash -w recovery recovery.img
# Boot into recovery
ubuntu-device-flash --server http://system-image.ubports.com touch --channel ubuntu-touch/rc-proposed