You simply have to keep a close eye and control over the memory you are using. Once memory gets accidentally overwritten, the symptoms can be very varied and hard to track down. Where memory is tight, try to avoid using run-time dynamically allocated memory (malloc/new). I appreciate you probably didn't know you were using it in this situation, but now you do.
You could start here for an intro into C-strings.
The cross test thing is likely because the compiler looks for "string literals" that are duplicated in the sketch and only stores them once. It then just references the one copy anywhere it is used. I don't recommend breaking them up as you have though as it impacts readability - that would be a last resort.
EDIT: Oh, and you could also try the F() macro to save some memory, though it may not be supported in every situation.