Well, I think is not actually the fully convolutional network, but the complexity of the task you are performing.
You could try, instead of using a fcn, use a normal convolutional network and check if the invariance provided by max pooling operators makes you learn something.