Phone Orange, they'll ask you for �20, which you can pay for either by taking off your current balance, or by giving them your credit/debit card details, wait a week, then they'll 'phone you and give you the code.
When you put the new SIM card in and it asks you for the unlock code, put the SIM unlock code in that Orange told you. Sometimes if you have a French 'phone like a Sagem, it can take up to 10 days because they need to contact Sagem in France for the code. (And companies like Orange don't like doing things quickly). Most Nokias can be done in under a week.
You can also go to practically any market stall or "dodgy" (i.e. no officially affiliated with any mobile network) shop in town and ask them to unlock it. It should only take two days, but they'll charge you around �20 too.