During the early months of 2005 I was an employee of a state
university in Florida. During this time the university failed to
withold FICA from my paycheck. Approximately 6 months after I stopped
working there, I received a letter from the university stating that I
need to pay them the FICA or the debt will go to collections. Am I
legally required to pay the university the FICA that it failed to
withold, or is it considered their responsibility to pay because they
did not withhold the FICA from my paycheck?

YES.  It is your responsibility to pay your share of the FICA.  Just
because they made a mistake does not relieve you of your cost share.