The same open rebellion did not get Tywin the least concerned before Jaime got captured. Why should all of them be concerned now besides for the sake of their beloved Jaime. If Robb did not beat any major army, they can still find him and crush him like they were sure to do before....if he did not beat any of their armies, they do still outnumber him and he is now further away in "enemy land" moving around with a relative small force compared to his foes.
And by the way....if Robb did not lift the siege at Riverrun, from whom is he gaining support then??? No one that we did listen about for sure so by all means, Robb is not gaining further support, this was not told yet. Actually, they even said otherwise, that he lacks allies and he is kind of desperate looking for support.....which goes a bit against your point. And you know why? Because if you delete the riverlands from the picture, Robb´s position gets even more frail then it was in the 1st place.