Go with the flow: Madeira

We have spent the best part of an hour criss-crossing the centre of Madeira's capital, Funchal, looking for what we have been told is the café where the city's young, stylish residents hang out. Despite a series of increasingly imprecise, if helpfully given, directions ("just behind the cathedral"; "up the hill, and sort of to the right, look for some steps") that kept bringing us back to where we started, we have finally found it, and it's shut.

Starving, we slope back towards the harbour and stop at the first café we come to, in a street of identical-looking tourist restaurants. The waiter produces a menu in English listing a range of "international" dishes that you know will have none of the glamour or style that this word somehow implies. Omelette and chips it is, then.

Last night we fared better on the food, but I can't say that our quest to find young, hip Madeira was any more successful. Umberto, the dapper erect-backed manager at our hotel, had recommended Doca do Cavacas, a fish restaurant built on what felt worryingly like the edge of a cliff. "Charming", "family", "modest" were all words that could have described this simple taverna, but not hip.

There was a simple menu that offered scabbard fish every which way, including with banana and mango. (Excuse the digression but just so you know, scabbard is a local delicacy, a fish that's caught only in the deep waters off Madeira and Japan and about which very little is known. Although, after seeing them for sale in a fishmongers, I can tell you one fact: it has looks that would make the Alien feel good about himself. The scabbard countenance is not helped by the fact that its eyes pop out of its head when it is dragged up from the high-pressure, dark depths.)

The clientele at Doca do Cavacas included a local extended family; a German couple with a rotund child of about three who wandered around the restaurant forcing slice after slice of bread into his ever-expanding hamster cheeks, and four middle-aged Brits who, after a day in the spring sun, were so red they looked as though they had been stoking a steam engine all day. The men wore that fetching combo of sandals with socks. We had a lovely meal, but it wasn't the Algonquin.

Yet something is happening in Madeira, even if it is hard to detect on the streets of Funchal. This Portuguese island, some 1,000km from Lisbon and 600km from the coast of Morocco, has a reputation for only attracting honeymooners and retired folk (a part of the holiday market rather bluntly known as "the newly wed and the nearly dead"), but now this conservative, slow-to-change Eden is home to several chic boutique hotels.

There's the Quinta da Casa Branca, an old wine merchant's estate close to the centre of Funchal, with just 43 rooms and two suites all tucked in among the bougainvillea and date palms. And Estalagem da Ponta do Sol, a cliff-top hotel with 54 rooms - all with sea views - on the south coast of Madeira, again not far from Funchal. Or there's Choupana Hills Resort and Spa, where I am slumming it for the weekend.

Owned by a German-Madeiran family - and their only hotel to date - Choupana is built high on the hills that overshadow the bay of Funchal (take a cab to Choupana, and you are in for an invigorating surprise as your confident/reckless driver navigates a succession of daunting hairpin bends without ever allowing his foot as much as to hover over the brake pedal). It's a magical setting, especially at sunset when you can watch the lights of the city flicker on and the cruise ships drop anchor in the harbour.

Dotted along a sloping plot, upmarket Choupana has 34 bungalows with two categories of accommodation: suites and deluxe rooms with sea or garden views. The hotel, built on the site of a former scrapyard, was designed by the French architect Michel de Camaret alongside architect-decorator Didier Lefort, who is also responsible for the Meridien Bora Bora and The Datai in Malaysia. Choupana's look is part-African, part-Asian: the bungalows look like safari lodges with their high-wood ceilings, dark timber floors and exotic four-poster beds; while the main building, where you find the restaurant and spa, looks Thai with its tall, angular roof.

Choupana is a long way from old-fashioned Funchal. Why, there are even young people staying here. But when I corner the manager, Philippe Moreau, he admits it has taken a lot of hard work attracting this new crowd of style-aware travellers to Madeira. Moreau says that many people are choosing the hotel because they think it looks like a great place to relax and are often arriving with little or no idea of what Madeira will be like. For the Louis Vuitton luggage contingent Choupana, not Madeira, is the destination.

And you can see the allure. There's the glorious setting, indoor and outdoor pools, a large spa and the smart Xopana restaurant with its fusion menu that mixes Asian, African and Madeiran influences. The seafood (scallops, tuna, that pug-ugly scabbard) is just-dragged-from-the-sea fresh. Portions are bountiful: as you waddle to the pool you'll be thankful that the locals have given up on their traditional pastime of whaling.

There's a calm, discreet level of service at Choupana that makes you feel cocooned from all the bad things in the world. As we laze by the pool, someone suddenly appears with an umbrella and a few words of warning about the harsh Madeiran sun. When we return to our room there's a plate of exotic fruit and a delicious bottle of Madeira wine.

The rooms have been designed so that when you look out at the bay you feel as though you are alone on the ridge - being so steep and lavishly planted, the hotel's other bungalows are shielded from view. You only have to be here a few minutes to feel your stress levels dropping - and ours were high after a very unwise decision to drive to Gatwick airport (never believe the AA route planner when it comes to journey times). At Choupana you feel they have thought of everything.

Yet what is there to appeal to these younger, stylish travellers when they finally manage to drag themselves away from the pool? There are very few nightclubs (although many of the hotels in Funchal put on a good show in the evenings, or so I am told) nor great bars - certainly none worth making the journey to the island for. There's also little in the way of shopping unless you are in the market for embroidered linen, and no beaches - although there are lot of places where you enjoy "sea access" from the rocks.

But there are excellent walks, great gardens and subtropical wild flora (the island is known as the "floating plant pot"), and British historical links which, for generations, have attracted middle-class tourists to Madeira. And it appears that these seemingly sedate, even old-fashioned attributes, are winning over the hearts of the younger tourists heading for Madeira. The walking is also a big hit, judging by the robust footwear sported by many of Choupana's guests at breakfast.

Madeira has an extensive water-supply system of open channels that run across vast areas of the mountains and countryside, irrigating crops and supplying villages. Some of the channels, known as levadas, date back to the 15th century; many were built by slaves. There is about 2,200km of these man-made streams and alongside them run pathways that offer an incredible - and on the whole, not too tiring - way of exploring Madeira (there are several good guide books that rate each trek for its degree of difficulty).

So, after failing to have a wild night in Funchal, and despite only having packed some special non-grip training shoes, we get with the programme and do the levadas - not to be mistaken with the lambada. Well, it isn't hard: one of them crosses through the middle of Choupana (occasionally, while you are poolside with a cocktail, you look up to see a couple of stout senior citizens swaddled in Gore-tex approaching you with what can only be described as a look of reproach for your lazy, hedonistic ways).

We head for the village of Monte, a walk of about 75 minutes. We amble through forests of fragrant eucalyptus, past banks of spectacular meadow flowers and walls of ferns kept moist by the sheets of spring water running off the hills. There are waterfalls, some vertiginous drops (slightly unsettling when you have the wrong footwear), panoramas to "Oooh" over and a lot of other British couples out for a stroll.

Everyone politely, and rather comically, tries to show good manners by letting each other pass first on the narrow path: "After you", "No, after you", "No, I insist, after you."

At Monte there are several picturesque churches (the exiled Austrian Emperor Charles I died in Monte in 1922 and is buried in the Nossa Senhora church); celebrated gardens and a cable car that takes you to the centre of Funchal - so you don't have to walk back along the same route. Even a short hike like ours makes you realise how stunning this island is and that the real lure of Madeira for visitors is the landscape.

Well, after that there is no stopping us. If the senior citizens are doing it we want our names on the list, too. So when there is mention of a hotel shuttle bus to see the annual Grand Flower Parade, we are first in the queue.

Supposedly a way for children to promote world peace, in reality the parade is an excuse to march some 1,700 children, from toddlers to teenagers, either dressed as flowers, sporting flowers, or sitting on flower-decked floats through the town. The children are divided into eight groups, each with its own not very different * *theme: "Sea of Flowers", "Sea Flowers", "I'm a Flower" etc.

The parade involves dancing to really strange choices of music - high-energy disco through to the Dambusters music. But, boy, is it a display of heartbreaking innocence. There is something moving about seeing the fat girl in class dancing with glee while dressed as an orchid; or the speccy boy having the best day of his life as he mimes to his dance number. An old woman, a local, turns to look at me and I see that tears are streaming down her face. I put an arm around her shoulder; I know just how she feels.

The streets are lined with senior citizen tourists, some just on Madeira for the day while their cruise liner pays a cursory visit. Others are old hands, like the wealthy widow who sat next to me on the flight to Funchal and told me that she comes to the island several times a year.

You can see why they all love the place: it feels safe, old-fashioned and reliable. And, of course, it is rather British - the link goes back to when Charles II married Catherine of Braganza and England gained trade concessions on the island. British troops were then stationed here during the Napoleonic Wars, too.

The arrival on the island of stylish boutique hotels is a good thing, but so too is the rest of the island being slightly out of step with the latest trends. In the end, it's simple things that make Madeira appealing: fresh air, having time to look at the plants, watching the ships sail past. Oh, and having a nice glass of Madeira at the end of the day (try Blandy's five-year-old Alvada that has been bottled to appeal to the kind of people who stay in hip hotels).

That doesn't mean that Madeira is standing still, or is being particularly robust about protecting its environment or way of life. Nasty-looking apartment blocks and timeshares are being built at a rapid pace. Many of the thousands of Madeirans who left to earn money in South America and South Africa (where there are said to be more people who call themselves Madeiran than there are on Madeira) are returning and bringing with them new attitudes. But for now, for the outsider, Madeira feels special. Just don't bother packing your dancing shoes.

MORE INFORMATION

Madeira Tourism (00 351 291 211 900; www.madeiratourism.org).