Very odd. It's possible that a factory reset is the solution, but it's a pain and it would be nice to avoid that. The first thing would be to double-check your blocking settings, though I'm sure you have and I can't see why a number would appear at random. You could also get him to call yoiu when you're next to each other and with a strong signal, just to check that's not the reason - again, if you haven't already.
It's possible it's also an app issue, so try going into Settings|Apps and the All tab and clearing the Phone/Call app's cache and force stopping it. I don't want to clear its data at this stage, though that would be the next step. It shouldn't affect your contacts, but it would (I'd assume) clear call logs and block lists and possibly other settings.
Before all that, if you haven't, of course, simply restart the phone. That sometimes kicks things back into life.
