I have a 15quid a month tarrif with vodafone, and because of various savings and discounts applied to my account my monthly bill is only about 18-20 quid a month..and I still got a free nokia 6230 when i upgraded over a year ago (around the time they were released). Initially I phoned up and was offered a samsung phone (urgh) but i complained to a few different reps, threatened to leave for another network (an empty threat, no way i was going to o2 and i couldnt afford orange's prices at the time) and they eventually decided to give me it for free
Granted this was with vodafone not orange, but I think it's the same with all networks.
Just keep trying and eventually they will give you what you want just to shut you up