TOM ALEXANDER was scathing. “The brand has lost a lot of its lustre with the general public. However many times they brush it up and change it, it doesn’t work.”

As he is the new chief executive of Orange UK, Alexander’s comments could be expected to send a chill down the spine of the mobile-phone group’s 12,500 British staff, not to mention his Parisian paymasters at owner France Télécom.

Just as well, then, that his remarks refer to his former employer BT, and are taken from an interview given two years ago.

But they still resonate when applied to Orange, whose future has never seemed as bright as its past since it was bought by the French for £25 billion in 2000.

Alexander has been drafted in after his success at Virgin Mobile, which he founded. In seven years, it amassed 4.2m customers. Then he led it on to the stock market and eventually sold it to NTL, now Virgin Media, for £960m.

In his first public outing since returning from a year’s semi-retirement, he is rather more diplomatic about Orange – and about why he has become the latest in a long line of executives charged with reviving an operation that even France Télécom boss Didier Lombard admits is a “special case” because it isn’t No 1 or No 2 in its home market. Some analysts think it could be sold if Alexander doesn’t succeed.

“The magic hasn’t gone,” he said, referring to Orange’s critics who hark back to the glory days of its founder, Hans Snook, who promised to make the mobile phone a “remote control for life”.

“The industry has changed and moved on,” said Alexander. “All the brands have grown and a number of other businesses have caught up with Orange in some areas. The values of the brand are more relevant today in many ways than when it was launched.”

The lure of trying to take Orange into first place – as measured by either customer numbers or revenues – appears to be one of the main draws for Alexander, who had pledged to spend more time with his wife and two small children. Orange once jostled with Vodafone for the No 1 slot, before O2 sped ahead and Orange dropped back to third. Today it has 15.6m UK customers, including 5.6m on a monthly contract. They spend an annual average of £265 each, up from £257 a year ago.

Alexander admitted: “The potential of the brand is one of the main reasons I joined. If it was No 1 it wouldn’t have got my interest as much.”

He certainly doesn’t need the money. He pocketed almost £25m from Virgin Mobile, and was sitting happily by the pool at his French retreat planning a season of motor racing in America when the call came from a headhunter.

Fixing Orange’s image is at the top of his list. Orange is the biggest spender on advertising in the industry, yet its campaigns – the latest, a rainbow of streamers proclaiming that “good things should never end” – merge seamlessly with those of rivals, all of which appeal to a cocktail of youngsters, music lovers and bargain hunters.

“Some of the representation of the brand has not been as effective as it could have been,” said Alexander. However, he likes the animals – raccoon, dolphin and panther – that badge each of Orange’s contract-pay-ment plans.

How much he can achieve with France Télécom watching will be interesting. Tensions between Paris and London defeated his predecessors. Laid-back Alexander insists he has enough autonomy to sort out the business. “What I didn’t get is a list of instructions. I have got great freedom to operate,” he said.

He has drafted in three Virgin Mobile colleagues – Andrew Ralston, Gerry McQuade and Steven Day – to help him out. They hope to recreate Virgin’s old “Crazy Gang” approach in Orange’s glass-walled headquarters at Paddington, west London.

However, Orange is much more complex than Virgin Mobile, which was essentially a slick sales and marketing outfit that piggy-backed on T-Mobile’s phone network. Alexander acknowledged that some of his quirky methods will have to be curbed.

The perception has been that Orange was starved of investment when France Télécom ran short of cash. Even now, Olaf Swantee, Alexander’s direct superior, has a firm eye on back-office functions that can be shared across the group.

Tough competition has undermined Orange’s profitability, although last year it had earnings of €1.4 billion (£1 billion), a rise of 2.2% over the previous year.

“The support from France is excellent,” said Alexander. “The great thing is that already we know we can do even better. There is no directive from on high saying take costs out. But there is an opportunity to make ourselves much more efficient.”

After a month at the helm, he is critical of Orange’s UK structure, which has “grown to have too many layers and too much bureaucracy”. He wants to try to overcome “some of the natural dogma that a large business has”. However, it is “too early to tell whether we will have more or fewer people”.

He is proposing a “rebalancing” in which swathes of box tickers will be switched into operational roles. In addition, Alexander is reviewing 2,000 call-centre jobs that were dispatched to India in 2006. He wants to make sure Orange is getting the “right quality at right cost” from the arrangement.

“We have to really cherish that customer relationship. That may be a change of focus.” Projects that distract from looking after the customer will be axed. Poor customer service is one reason why Orange took its foot off the gas in the pursuit of broadband customers. It has 1.1m, but has lost momentum.

Sky, a new rival 39% owned by News Corporation, parent company of The Sunday Times, has amassed the same number in less than 18 months. Orange’s efforts to cross-sell to its mobile customers have fallen flat, with only about 350,000 phone subscribers signing up for a fast-internet connection.

Alexander said: “We are reviewing all of the businesses to look at how we build them.

We are definitely not grooming it [the broadband division] for sale.”

He wants to build up other services around mobile and broadband, such as music and entertainment. Central to that is a television service over broadband that is still on trial in London and Leeds. Orange cancelled a preChristmas launch and Alexander won’t say when it will be rolled out.

Despite his return to work, the fun is not over for Alexander. He is racing in the British GT Championship at the end of March.

And while the rest of his industry is heading to Barcelona for the Mobile World Congress this week, he is going on a long-planned skiing trip – after attending tonight’s Bafta film awards, which Orange sponsors.

Times Recommends

• Lies and cover-up at MG Rover exposed by report
• High oil prices push manufacturing costs up
• Primark founder steps down as chief executive