Workaround:
ClearAll["`*"]
randomNums = Table[{x, Sqrt[5^2 - x^2] + Random[]}, {x, -5, 5, 0.5}];
nlm = NonlinearModelFit[randomNums, a Re[Sqrt[b r^2 - c x^2]] + d, {a, b, c, d, r}, x] // Quiet
Show[{ListPlot[randomNums, PlotStyle -> Black], Plot[(nlm // Normal), {x, -5, 5}, PlotStyle -> Red]}]
For more information see: here, here and here.
