Are you being paid to take the training?

If so then I probably would continue training and being paid while looking for a job. If not - then I would stop the training (as you said they are worthless without the extra experience of working after) and look for a new job.

Unfortunately once a company says that you "may need to find a new job" it's almost certain that you will need to.