iPhone app has frozen phone. Now what?

This is an interesting problem and, of course, one of the pervasive nightmares of both device owners who freely download applications and companies like Apple who are stuck between the proverbial rock and a hard place, wanting to have a rich, vibrant application marketplace but also needing to ensure that downloading an app from Apple doesn't freeze, brick or otherwise kill your phone.

Digging around on Google for information about the "Call Me" application from Cydia, I realized that you have omitted a very important piece of information: you've "jailbroken" your phone (that is, hacked the system so that you aren't running the stock Apple iPhone software any more). I understand the lure of freeing your gadget from the constraints of the corporate overlord :-) but as I hope you realized when you did jailbreak the phone, there's a risk involved. A big risk.

Your situation illustrates the risk very well: if you move into your own world with all of this, eschewing Apple's carefully crafted operating system for the phone, then you really are on your own and are far more at risk for malware, viruses, and bricking your phone.

Now, to fix it, I would say that your best bet is to hook it up to your computer, launch the iTunes application and choose "Restore", then go have a cup of tea or walk around the neighborhood. It'll take a while. (here's a more detailed article on the subject: How to restore your Apple iPhone)

When it's done, you should have a fully functional non-jailbroken phone that has no music, no videos, and, most likely, no additional applications. At this point you can re-jailbreak it (and, again, I have an article on the subject: How to jailbreak your Apple iPhone) or leave it as a "jailed" phone and rest comfortably that it's going to be far more stable and reliable and that the 10,000+ applications in the iPhone App Store are most likely going to have just about everything you need anyway.

Good luck and let us know how it goes!