I finally figured out what is the problem. For anyone who is running into problems like this, the following could be helpful:
I have a binary segmentation mask. The labeling was done in LabelMe.
The output of LabelMe are are images and the corresponding labels both in RGB-Values.
I converted the RGB Values of the label into greyscale.
The resulting greyscale image MUST include only values between [0 … (num_classes -1)]. For a binary problem one has to convert the (arbitrary) color-numbers into 0s and 1s (0: background, 1: class of interest). This solved the issue for me.