Are the labels updated during training in the algorithm presented in "An algorithm for correcting mislabeled data"?
I think that making some draws might help.

Below I tried to draw the model architecture. We start with classic feed-forward structure: input represented by a vector I with length f (number of features), a hidden layer H which does not have a fixed size, and output O of length c (number of classes). Then we have 3 extra vectors than usual:
a vector U they refer as input (a bit confusing I have to say), and two vectors V and P representing classes probabilities. All these vectors have length c.

P is what we want to learn, new class probabilities for each instance that should correct wrong labels of misclassified instances in the initial dataset.
So in some sense the aim of the work is not to train a model to make predictions but rather train a model to clean a training dataset. I think it's important to stress out this point because we talk about training but there is actually no test after the training, we just end with a modified training dataset with some instances relabelled. 
The relabelling depends on the learning of V rather than P (because as I will say also later on, the final arrow that goes from V to P is the identity function). V depends on U that also depends on V, again it sounds a bit confusing, the tricks rely in the initialisation. 

In the second picture I just copied some formulas from the paper. They don't specifically say how they get the vector P in the first place, but I treat it simply as given because we need it to initialise U by applying the inverse sigmoid function, element-wise. We need also to define the hyper parameter D, the initial probability value for the true class V$_y$ in the initial dataset. In the paper they set it to .95. Using D we can initialise the vector V.

Once we initialise U and V we have all the elements to iterate over the dataset. 

A first thing to notice is that they don't use back propagation to update U,V and P, they just define some updating rules (which require to define some other initial parameters, $\textit{u$_0$}$ and L$_p$). I want to stress out again that the mapping between V and P is just the identity function, I guess that they define it just to avoid confusion, because in the paper P appear as an input element, but nevertheless is also the output we want to learn. Back propagation is used only to update the weights in H. 

ANSWERS TO THE QUESTIONS:

So we can finally say that, regarding your first question, the answer is yes, they do start updating the classes probability vectors P from the very first iteration, even though is not clear how they initialise them (or from where they got them). 

Regarding the second question instead I would say that no, this is definitely not as training a model with fixed label and then making predictions over the training dataset again. The whole point is that similar training instances will be initialised with the same P, and they will also produce similar U and V vectors. For misclassified instances, U will be updated with larger changes, because of the different produced O. For example an image of a 2 will generate a different output than an image of a 5, this would be reflected first on U and then on V and P . If training with fixed label instead you would just force the weight in the hidden layer to learn a function that treat the representation of a 2 and a 5 in a similar way, leading to low accuracy cause you would be telling the model "Hey, the straight line in the 5 is important also to recognise a 2". 

I have to say that I never read about this dataset cleaning approach but it is interesting, and their results show that the cleaned version of the dataset lead to better performances, which is interesting because machine learning analysis usually gives for granted the correctness of the labels. 

Hope this is of help in some ways!