Have I waited too long to ask for letters of recommendation and when should I send a follow up email?
No. You gave enough time for them. However you can't count the holidays as work days, they are coming back to work in the next days and then they will have approximately three weeks to write the letter. 

I would send an email at the end of this week politely asking the second professor to confirm whether he will be able to write the letter or not. In the negative case you still have enough time to ask to another professor.