The application as a whole has to work & be somewhat stable. If some other class suddenly started to fail check if there's a relation between what you're doing and what this class is about. Maybe there's something indirect (via trigger for example)? Maybe somebody made a change on production that suddenly broke the functionality. A good example is a new validation rule or a new required / unique field.
Maybe your unit test relies on production data that changed in the meantime?
Check if the unit test of this "broken class" fails also when just run the test execution on production. If they fail you know something changed. if they pass - it's most likely something in your deployment that breaks them. Try to run it from Eclipse / Data Migration tool if possible, if not - just use web interface.
As mast0r said - you need total 75% or better across your whole codebase (classes and triggers). And of course no errors.