I think you need to add a lot more detail to your site to make it work.
Agreed, gmail contact is totally wrong. Google Apps has an excellent mail server that will use your domain assuming you don't have a built in mail server with your hosting. Then, every link to your e-mail is an ad for your website.
I like a "Contact Us" page with phone numbers, address and probably a form that: 1 blocks some spam and 2 requires the guest to provide some basic details.
I would place the address at the base of every page. You're in a Location type business and address is the starting point of identifying your location to Google that will later appear in Maps results. It is amazing how much Google Maps sells accommodation as well as a growing number of sales from Google Earth. Check your placement in Google Maps and Add or Edit your listing.
Get a Map. You could just post an image of a map. People tracvelling want to know where you are (near the GPO, beach, train station, etc.) I would either use a website tool with inbuilt mapping, or go to Google Maps, create a My Map and then use their embedded link to place this map on your website in an iframe. As a keyword, Map of Malacca is a really powerful term to have on pages.
What is the Trip Advisor logo for? I understand that there might be a process where you can link User Reviews sourced from Trip Advisor using RSS. Is that your intention?
Images - you need to work here much more. Images of the exterior, location, images of all the rooms, restaurant and facilities, etc. People are very focused on images.
YouTube - we started adding embedded YouTube links to pages to make them seem much more lively. It is very easy to do. here's an example -
Golden Chain - Beachfront Motel & Cottages - Apollo Bay Just do a search on topics related to your location and you'll find all sorts of things that can be free content.
You appear to have 2 Hotels. This needs to be clarified. If there are 2, display them both and let people know their locations, features and see differentiated images.
Your Rate Tables display various Room Types with 3 seasons. Essentially, the buyer has no way to know what it will cost and whether they can get a room. This types of page needs to be more functional. There are lots of booking system options. You should get one. People flying in from overseas don't want to call you and sending an unstructured e-mail to a gmail acount is not good business. In the perfect world you would have the ability to provide immediatly confirmed bookings that are secured by a credit card. If you're business suits the inbound market, then a good booking system would also link you to the GDS systems that feed TripAdvisor as well as airline ticketing systems.
Beef up the Location Info. This is great keyword fodder and people like to know what they can do when they arrive.
Some people would suggest you need rates in both local currency and US dollars to help people understand costs. You say your rooms are "cheap", but when I see rates in RM I have no point of reference.
Agreed, you need to make sure your internal links from page to page are correct.
You might ask a traveller with Native English to go through your copy. There are some small mistakes. Also work your keywords more to attract the long tail search. Perhaps you need to use Malaysia in your title tags and on the page. Again, placing your address at the base of every page can help.
Location - for Google they determine location by domain extension or hosting. You have a dot com domain, which indicates you are in the US. I haven't checked your hosting. If it is not in Malaysia, then you need to use Google Webmaster tools to correct the false impression that your business is located in other parts of the world. In travel, location results seem very important to me.
Good Luck. You've made a nice start. Shouldn't be to hard to improve.