Unicorns were supposed to be mythical creatures, which Phoenix is too - so that works.
But Phoenix has a negative connotation with the burning into flames part. Not sure if many startups would like to call them Phoenixes :)
What about pegasus? Even better would be a pegacorn/alicorn, but not enough people are familiar with those names. It seems like the natural next step would be a unicorn that's taken flight.