I think the problem is that you can't prove there ever was a fire Frostyspecs - or that your old phone was destroyed in one. From O2's point of view, there are so many dishonest and disreputable people who will say and try anything if it suits them. Such individuals would think nothing of fabricating some story to O2 if they thought they could get a free upgarde whenever the fancy of a new phone took them.
You entered into a contract with O2 for a particular phone. O2 don't know you aren't one of those who just fancies upgrading but who has every intention of avoiding the costs if they can possibly do so. From O2's point of view, they still want their contract with you honoured. Why should they lose out if you had a fire? O2 would tell you to claim for the lost phone and costs on your fire insurance. If you don't have insurance, they would argue - more fool you.