Although I dont know any secluded areas near Phuket, I agree with MarkAdmin...."Why Patong?".
Patong is the only area in Thailand I never really liked for some reason.

Just a note- in my previous post I said I wouldnt go to Phuket- To clarrify I meant Patong. Parts of Phuket are amazing, its just Patong that I found to be very touristy and dirty...
Grace

__________________
STAY AWAY FROM MONKEYS!!!!

You don't say when you are going!

November- April best in Phuket, Samui opposite.

For young people like you and even for an older guy as myself, if you don't mind not being very close at the beach, the place rent bikes;

Cottages - Boomerang Village Cottages

Fantastic cottages, tasteful decorated and very, very nice guys running it. It is on a hill. Kata beach is at 5 minutes with the bike and Kata starts on the other side of the road. Around 2000 bht /night
For further away:

Take the boat to Phi Phi, you can then cross to Lanta and from there all the smaller islands in Trang province, like Koh Hai.

On this page, you can see the trip I have done 2 years ago:

cambodiathailand_20067 Photo Gallery by Indieke at pbase.com

Seen the second part after Cambodia.

I haven't been to Phuket post Tsunami but have spent considerable amounts of time there before. My feelings are Patong's OK as long as you remember it's a party town, so if you want laid back tropical ambience then Patong's probably too "in your face" Personally I think Patong bay/beach is the most scenic on the island, which makes sense as they developed the best beach first. However, I've never enjoyed swimming at Patong as the seawater always seems itchy, I don't think it's pollution or anything like that, maybe just some minute marine life. The biggest turnoff for me at Patong are the greedy & inconsiderate Thais, the songteaw men and the rip-off street stalls, and the young louts that hang around making pests of themselves. There used to be lepers begging on the streets after dark too, I remember my mother was fascinated on one holiday as she's never seen lepers before.

__________________
The Truly Wise Man Never Plays Leapfrog With A Unicorn

If you're thinking of a picturesque island a bit less developed than Phuket, why not check out Koh Tao over in the Gulf of Thailand. You can get from Phuket or BKK to Koh Tao in less than one day and it's well worth the effort.
With a 200AUD per night budget, check out the quality Sairee Beach accommodation at Koh Tao Simple Life Resort.
Or if you really want to go rural, check out Koh Lipe or Koh Payam off Thailand's west coast - these are the new upcoming islands that are still off the beaten track which needless to say, also means trickier to get to.