Sort Order, Locale and PostgreSQL

[KSoftware]

As I understand it locale effects sort order, and locale can only be set at initdb time. I have a customer complaining about the string sort order of one of his queries.

This is a database of Christian songs, so..

songs2=> select title from songs order by lower(title);
title
------------------------------------------------
I Believe in Jesus
I Come With Joy
I Do Believe
I d Rather Have Jesus
I Exalt Thee
I Extol You
If That Isnt Love
I Heard the Bells on Christmas Day
I Love You Lord
Immortal Invisible God Only Wise
In All Things Give Him Thanks
Indescribable
I Need Thee Every Hour
Infant Holy Infant Lowly

You can see the odd sorting going on. Apparently the spaces are being totally ignored.

is there any way to change (or even check!) the locale of a PostgreSQL database under Plesk 7.5.4 running on a fedora core 2 box?

If the locale isn't at fault there, any other help is appreciated! I don't know what to tell this guy!