When should I start applying for a PhD program in the UK?
Funded PhDs in the UK usually follow the academic calendar and start in late September or early October. Accordingly, application deadlines tend to be in February or March (often set by the funding councils and hence will be the same for every university). 

The exception to this is if you are planning to self-fund your PhD, in which case you will have more flexibility on starting dates (but check with the universities you are going to apply to if you are planning to do this).

The best time for you to submit your applications is probably as close to the deadline as possible, especially if you want to use your supervisor/ tutor/ other lecturer from your MSc as a reference. The longer you wait to submit the application, the better they will get to know you and hence be able to write a better reference.

However, don't wait until the last minute to ask for a reference! Ask well ahead of time (>1 month) and let them know when the application deadline is so they have time to prepare.