Before removing the toilet...
As you were tightening it, it's entirely possible that the bolt turned 90°, coming loose in the flange slot, and that's the sudden loosening you felt.
Here's an image of a toilet flange. The nifty red line/oval are my own addition showing where the bolt is supposed to go. Note that this flange image is upside down from the way it's actually installed in your floor:

Flange image courtesy of homedepot.com. Red bolt courtesy of my excellent artistic skillz.
Hat tip to Steve Summit for suggesting inclusion of a picture.
You can see that the bolt head is oval shaped to fit through the oval hole in the toilet. It also fits through the keyhole slot in the toilet flange. My guess is that nothing at all is broken and that it's a very simple fix. Even if I'm wrong, this is a cheap, simple thing to try before you start removing things and buying parts.
- Place the bolt down through the slot in the toilet, pushing it all the way down until it stops moving.
- Keeping the bolt vertical and applying light pressure, carefully rotate the bolt 90° (either direction).
- Once the oval bolt head lines up with the slot in the toilet flange, it should drop right through.
- Carefully rotate the bolt another 90° (again, either way).
- Pull up on the bolt.
- It should now be caught by the flange, and should not start coming back up to hit the porcelain.
- Assuming the bolt is caught, hold the bolt and start the nut.
- As you tighten the nut, continue to pull up on the bolt, moving your grip as necessary, to hold the bolt in its caught position.
- Once the bolt is snug enough, it shouldn't spin as you finalize tightening the nut.
It might be helpful to take a Sharpie™ or other marker pen and draw a line on the flat at the end of the bolt (the part that will point up as you're tightening the nut down) that is in line with the length of the oval head. This line will help you to keep track of which way the oval is facing, and it will help you to keep the bolt aligned as you're twisting, turning and tightening.