Getting Letter of recommendation with letter head
There shouldn't be an issue if they use letterhead of their present employer. They will probably say something about the change of affiliation. But it might be improper for them to submit on the old employer's letterhead. 

But a letter on plain paper should also be fine, assuming that the letter writer provides contact information so that their affiliation can be checked if necessary. 

Or you can also indicate in application materials that the affiliations of letter writers are new. 

Note that I'm retired and so have no current affiliation, but my last employer is happy enough for me to use their letterhead and has provided me with an electronic template for it. Perhaps that is available to your writers as well if it seems important.