To tell you the truth, I'm always split on this issue. I feel that C is better for learning the basic programming concepts, and makes you appreciate Perl more once you get to it. The other side is that by learning Perl first, you get to build interesting things a lot faster and in doing so often keep the student more interested. So it does depend on the student somewhat, if they're really interested in programming in general I'd definately recommend learning C first. Otherwise it's a toss-up, and since I'm terribly biased towards Perl, I often recommend C just to maintain some shred of objectivity ;-).
I definately agree with your point that learning Perl helps one understand C better, I know this was true for me. I also believe the reverse is true, C helps you understand Perl better (some experience in a *nix environment helps as well). Keep in mind, Whatever people think about C vs Perl as an introductory language, at least they're both not Java :)