I'm training a deep network (CNN-LSTM-CRF) for Named Entity Recognition. Is there a reason that increasing the number of parameters would make the network less able to overfit a small training set (~20 sentences), or does this indicate a serious bug in the code?
It is not necessarily a red flag. Of course, without seeing the code, it is impossible to say that for sure.
What is likely happening here is that adding parameters to your model, it makes it harder for it to converge to some minimum. More parameters roughly mean that your model is able to explain "more complex stuff". And since you have a small amount of data, the explanation should remain rather simple. Therefore, your model is trying to explain something simple in a complicated way, and it might not be easy to do so.
Also, are you using dropout or regularization? If yes, this might also be an issue as these are explicitly use to avoid overfitting.