The public holiday that you stated below, company only observe 2 of them which is Selangor Sultan Birthday(11 December 2015)  and Christmas(25 December 2015). While Selangor won Malaysia cup( 14 December 2015) and Prophet Muhammad(24 December 2015) is not compulsory public holiday which our company did not observe.

EMPLOYMENT ACT 1955
EMPLOYMENT (PART-TIME EMPLOYEES) REGULATIONS 2010

Holidays
6. (1) Every part-time employee shall be entitled to a paid holiday at his
ordinary rate of pay on the following days in any one calendar year:
(a) on not less than seven of the gazetted public holidays, four of which
shall be—
(i) the National Day;
(ii) the Birthday of the Yang di-Pertuan Agong;
(iii) the Birthday of the Ruler or the Yang di-Pertua Negeri, as the case
may be, of the State in which the part-time employee wholly or mainly
works under his contract of service, or the Federal Territory Day, if the
part-time employee wholly or mainly works in the Federal Territory; and
(iv) the Worker’s Day; and
(b) on any day declared as a public holiday under section 8 of the
Holidays Act 1951 [Act 369].

Reference: http://www.ilo.org/dyn/travail/docs/1527/E...aonline.net.pdf

[Section 3]
PUBLIC HOLIDAYS
Birthday of the Prophet Muhammad (s.a.w.).
Hari Kebangsaan or National Day.
Chinese New Year (one day in the States of Kelantan and Terengganu, two
days in the other States).
Wesak Day.
Birthday of the Yang di-Pertuan Agong.
Hari Raya Puasa (2 days).
Hari Raya Haji (two days in the States of Kelantan and Terengganu, one day
in the other States).
Deepavali.
Christmas day

Reference: http://www.ilo.org/dyn/travail/docs/1526/H....agc.gov.my.pdf

Issue I'm facing currently.

1) There are a total of 4 public holiday back in December 2015. The public holiday are as follows;

Dec 11 - Selangor sultan birthday
Dec 14 - Selangor won Malaysia cup in football. It was declared as public holiday
Dec 24 - Prophet Muhammad birthday
Dec 25 - Christmas

2) I worked on all public holiday in December but in my payslip only stated that only 2 out of 4 public holiday is entitled for public holiday pay.

3) I decided to email the HR department regarding this. The HR replied me and I had included the their reply in the quote below
4) Right after I received their reply, I immediately check my agreement. It stated clearly that all benefit is accordance to EMPLOYMENT ACT 1955
EMPLOYMENT (PART-TIME EMPLOYEES) REGULATIONS 2010

5) I went and google the act and found the following;
6) Since it is stated in the Employement Act 1955 that 'on any day declared as a public holiday under section 8 of the
Holidays Act 1951', I decided to take a look at Holiday Act 1951 and found that
7) It is stated clearly that Prophet Muhammad birthday is a public holiday but the HR said not compulsory PH which the company did not observe. Therefore, we are not entitled for PH special pay rate on 24th December. However, my agreement it stated that it follows EMPLOYMENT ACT 1955
EMPLOYMENT (PART-TIME EMPLOYEES) REGULATIONS 2010 but it did not say how many PH and which PH is entitled in my agreement.

So now I wanna ask,

- Is the company at fault now? It's all stated black and white. If company is at fault, what should I do next?
- Is the company being not ethical by telling us Dec 14 and 24 is public holiday before the actual working day. But after working day, it is considered as not PH and they did not tell us a single thing about it. Actually I'm not supposed to work on Dec 14 and 24 2015 but because they said its PH, therefore its compulsory to work. Unfortunately, I do not have any solid proof that the company told us this because we talk face-to-face instead of messaging etc.
- Some of my colleagues (full-time) that worked OT but company did not pay for it. Can we sue the company regarding this?

Employment Act 1955 Section 60D
(1) Every employee shall be entitled to a paid holiday at his ordinary rate of pay on the following days in any one calendar year:

(a) on eleven of the gazetted public holidays, five of which shall be—

(i) the National Day;

(ii) the Birthday of the Yang di-Pertuan Agong;

(iii) the Birthday of the Ruler or the Yang di-Pertua Negeri, as the case may be, of the State in which the employee wholly or mainly works under his contract of service, or the Federal Territory Day, if the employee wholly or mainly works in the Federal Territory;

(iv) the Workers’ Day; and

(v) Malaysia Day; and

(b) on any day appointed as a public holiday for that particular year under section 8 of the Holidays Act 1951 [Act 369]:

Provided that if any of the public holidays referred to in paragraphs (a) and (b) falls on—

(i) a rest day; or

(ii) any other public holiday referred to in paragraphs (a) and (b),

the working day following immediately the rest day or the other public holiday shall be a paid holiday in substitution of the first mentioned public holiday.

(1A) The employer shall exhibit conspicuously at the place of employment before the commencement of each calendar year a notice specifying the remaining six gazetted public holidays provided for in paragraph (1)(a) in respect of which his employees shall be entitled to paid holidays under paragraph (1)(a):

Provided that by agreement between the employer and an employee any other day or days may be substituted for one or more of the remaining six gazetted public holidays provided for in paragraph (1)(a):

And provided further that the employer may grant the employee any other day as a paid public holiday in substitution for any of the public holidays referred to in paragraph (1)(b).

(1B) Where any of the public holidays or any other day substituted therefore as provided in subsection (1) or (1A) falls within the period during which an employee is on sick leave or annual leave to which the employee is entitled under this Act, or falls during the period of temporary disablement under the Workmen’s Compensation Act 1952, or under the Employees Social Security Act 1969, the employer shall grant another day as a paid holiday in substitution for such public holiday or the day substituted therefore.

(2) Any employee who absents himself from work on the working day immediately preceding or immediately succeeding a public holiday or two or more consecutive public holidays or any day or days substituted therefore under this section without the prior consent of his employer shall not be entitled to any holiday pay for such holiday or consecutive holidays unless he has a reasonable excuse for such absence.

(2A) An employee on a monthly rate of pay shall be deemed to have received his holiday pay if he receives from his employer his monthly wages, without abatement (other than as provided under subsection (2)) in respect of the holiday, for the month in which the holiday falls.

(3) (a) Notwithstanding subsections (1), (1A) and (1B), any employee may be required by his employer to work on any paid holiday to which he is entitled under the said subsections and in such event he shall, in addition to the holiday pay he is entitled to for that day—

(i) in the case of an employee employed on a monthly, weekly, daily, hourly, or other similar rate of pay, be paid two days’ wages at the ordinary rate of pay; or

(ii) in the case of an employee employed on piece rates, be paid twice the ordinary rate per piece,

regardless that the period of work done on that day is less than the normal hours of work.

(aa) For any overtime work carried out by an employee referred to in subparagraph (a)(i) in excess of the normal hours of work on a paid public holiday, the employee shall be paid at a rate which is not less than three times his hourly rate of pay.

(aaa) For any overtime work carried out by an employee referred to in subparagraph (a)(ii) in excess of the normal hours of work on any paid holiday, the employee shall be paid not less than three times the ordinary rate per piece.

(b) An employee who works on a holiday shall be entitled to a travelling allowance for that day if payable to him under the terms of his agreement with his employer but such employee shall not be entitled under this subsection to receive an increased rate of any housing allowance or food allowance.

(4) For the purposes of this section if any such holiday falls on a half working day, the ordinary rate of pay payable shall be that of a full working day.

- Is the company at fault now? It's all stated black and white. If company is at fault, what should I do next?
- Is the company being not ethical by telling us Dec 14 and 24 is public holiday before the actual working day. But after working day, it is considered as not PH and they did not tell us a single thing about it. Actually I'm not supposed to work on Dec 14 and 24 2015 but because they said its PH, therefore its compulsory to work. Unfortunately, I do not have any solid proof that the company told us this because we talk face-to-face instead of messaging etc.

- Some of my colleagues (full-time) that worked OT but company did not pay for it. Can we sue the company regarding this?

New to work ka brother?

According to Employment Act 1955 Section 60D. (Which you had quoted, but not fully.)
Refer to the above bolded parts.
Your company should inform you in two ways regarding the company's public holiday (minimum of 11 days), in the Employment Contract and Internal Memo.

As long as the days are not in the list, you will not be entitled to received holiday pay. If you do work on the days listed in the Holiday List of your company, you will be paid double. If there is OT, triple rate for OT.
For overtime, again refer to your contract for NORMAL WORK HOURS and OVERTIME clause.

If employer explicitly stated no overtime will be paid, then you should not do overtime.

So again, check your contract.