Good luck then.
So, the problem was with newly mined coins
I would say the problem is with the client and not with the newly mined coins. The two other clients I have used don't have this problem.
I'd agree here. I was having the same error a few weeks back after my wallet was dormant for several months - at first I thought it was an issue with fees, but some google'ing denied that and redoubled frustration. It took an hour and an Ubuntu installation to get anything working again. I'm not sure I'll be sticking with Electrum after that fiasco - it ruined a trade, but I guess that's partly my fault.