All of Asia,Nepal, India, Europe, Australia, New Zealand (Kiwi Exprience is geard for solo travelers) are very easy and fun to do solo, try to stay in Hostels and meet other travellers.
You can even go on a Safari in Southern Africa solo, they have these Safari tours for Solo backpackers. Zim\Zam tours.