Why are KMeans cluster labels not always the same with set random_state?

I have a notebook where I want to analyze the clusters from sklearn.cluster.KMeans. When I run the code, the clusters are the same, but the labels applied can vary. This makes it impossible for me to refer to a cluster by label in the markdown sections of the notebook. I am wondering why this occurs even when setting the random_state. It appears that random_state is only allowing for the clustering to be the same, but why does it not also apply the same label values each time? The code below will replicate the issue and the plot shows how the labels can vary.

from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt

np.random.seed(2)

x = np.random.normal(size=(1800, 2))
x[:700, 0] += 3
x[:700, 1] += 3
x[700:1200, 0] -= 0.5
x[700:1200, 1] -= 0.5
x[1200:, 0] += 3
x[1200:, 1] -= 3

np.random.shuffle(x)

first = None
while True: # it typically only takes a few iterations for a difference to occur
    km = KMeans(n_clusters=3, random_state=10)
    km.fit(x)
    pred = km.predict(x)
    if first is None:
        first = pred
    elif not np.array_equal(first, pred):
        print(first)
        print(pred)
        fig, ax = plt.subplots(1,2)
        for label in range(3):
            clusters = x[first == label]
            cluster = x[pred == label]
            ax[0].scatter(clusters[:, 0], clusters[:, 1], label=label)
            ax[1].scatter(cluster[:, 0], cluster[:, 1], label=label)
        break

ax[0].legend()
ax[1].legend()
plt.show()

[0 1 1 ... 2 0 0] # labels for first run
[0 2 2 ... 1 0 0] # different labels for later run

Furthermore, I am confused as to why the verbose output is not exactly the same when using the same random_state.

I have noticed a couple of things. First is that np.random.seed(1) will not generate this problem. So, it appears to be data-dependent. Second if n_jobs=1 this doesn't seem to occur but the default n_jobs=None gives different results (both labels and verbose output). Is the parallelization causing this to happen?

It would be good to know if this is a bug that I should report to scikit-learn devs or if this is a an issue specific to my case that will require a work-around.