PostgreSQL 9.1 streaming replication problem: replica fails to use an index properly
Assuming the locale of the database is en_GB.UTF-8 both in Ubuntu (master) and FreeBSD (slave), I believe the differences in sort semantics alone may account for the fact that the index is unusable on the slave.

Here's an example of how they sort differently:

On Ubuntu 12.04:

$ export LANG=en_GB.UTF-8
$ cat &gt;file
"0102"
0102 
$ sort file
0102
"0102"


On FreeBSD 9.0-RELEASE:

$ export LANG=en_GB.UTF-8
$ cat &gt;file
"0102"
0102
$ sort file
"0102"
0102


This shows that the same locale orders differently the two strings "0102" and 0102 (even though they do not even contain any character outside the US-ASCII set...)

Here's a test that I suggest you try on your own dataset:

On the master:

$ psql -d dbname -Atc 'select email from users' | LC_COLLATE=en_GB.UTF-8 &gt;email.master


On the slave:

$ psql -d dbname -Atc 'select email from users' | LC_COLLATE=en_GB.UTF-8 &gt;email.slave


Now compare email.master and email.slave with diff or cmp. I suspect you'll find that they are not identical. In which case it demonstrates that the index replica can't be used, since its build rules on the master differ from the scanning rules on the slave.