Is C collation suitable for my Postgres database?
From what you're describing, it doesn't sound like anything is contraindicated related to the C collation order. In fact, Robert Haas, has a great discussion on the subject here, which seems to come to the conclusion that if you don't need locale aware sorting, just don't use it: Perils of Collation Aware Comparisons

I did notice you are on Debian Wheezy. The stock kernel for Debian Wheezy is 3.2, which if you're using that, has abysmal performance on database workloads. I would investigate that along with the collation testing, if you are not happy with the performance of your machine. 

The wheezy-backports kernel is 3.16, which does not have these issues. Discussion and performance tests are here: Benchmarking PostgreSQL with Different Kernel Versions

Hope that helps. =)