Please run this code and print its output here:

<?php
phpinfo(INFO_GENERAL);
echo "\n\n<br />\n\n";
var_dump( nl2br("foo isn't\n bar") );
?>

If something sensitive appears in there, remove it first.

Philip, 
Here is the output as requested:

string(20) "foo isn't<br>
 bar"

System 	Linux localhost 2.6.18-53.el5 #1 SMP Wed Oct 10 16:34:02 EDT 2007 i686
Build Date 	Sep 12 2007 11:11:33
Configure Command 	'./configure' '--build=i686-redhat-linux-gnu' '--host=i686-redhat-linux-gnu' '--target=i386-redhat-linux-gnu' '--program-prefix=' '--prefix=/usr' '--exec-prefix=/usr' '--bindir=/usr/bin' '--sbindir=/usr/sbin' '--sysconfdir=/etc' '--datadir=/usr/share' '--includedir=/usr/include' '--libdir=/usr/lib' '--libexecdir=/usr/libexec' '--localstatedir=/var' '--sharedstatedir=/usr/com' '--mandir=/usr/share/man' '--infodir=/usr/share/info' '--cache-file=../config.cache' '--with-libdir=lib' '--with-config-file-path=/etc' '--with-config-file-scan-dir=/etc/php.d' '--disable-debug' '--with-pic' '--disable-rpath' '--without-pear' '--with-bz2' '--with-curl' '--with-exec-dir=/usr/bin' '--with-freetype-dir=/usr' '--with-png-dir=/usr' '--enable-gd-native-ttf' '--without-gdbm' '--with-gettext' '--with-gmp' '--with-iconv' '--with-jpeg-dir=/usr' '--with-openssl' '--with-png' '--with-pspell' '--with-expat-dir=/usr' '--with-pcre-regex=/usr' '--with-zlib' '--with-layout=GNU' '--enable-exif' '--enable-ftp' '--enable-magic-quotes' '--enable-sockets' '--enable-sysvsem' '--enable-sysvshm' '--enable-sysvmsg' '--enable-track-vars' '--enable-trans-sid' '--enable-yp' '--enable-wddx' '--with-kerberos' '--enable-ucd-snmp-hack' '--with-unixODBC=shared,/usr' '--enable-memory-limit' '--enable-shmop' '--enable-calendar' '--enable-dbx' '--enable-dio' '--with-mime-magic=/etc/httpd/conf/magic' '--without-sqlite' '--with-libxml-dir=/usr' '--with-xml' '--with-apxs2=/usr/sbin/apxs' '--without-mysql' '--without-gd' '--without-odbc' '--disable-dom' '--disable-dba' '--without-unixODBC' '--disable-pdo' '--disable-xmlreader' '--disable-xmlwriter'
Server API 	Apache 2.0 Handler
Virtual Directory Support 	disabled
Configuration File (php.ini) Path 	/etc/php.ini
Scan this dir for additional .ini files 	/etc/php.d
additional .ini files parsed 	/etc/php.d/gd.ini, /etc/php.d/ldap.ini, /etc/php.d/mysql.ini, /etc/php.d/mysqli.ini, /etc/php.d/pdo.ini, /etc/php.d/pdo_mysql.ini, /etc/php.d/pdo_sqlite.ini
PHP API 	20041225
PHP Extension 	20050922
Zend Extension 	220051025
Debug Build 	no
Thread Safety 	disabled
Zend Memory Manager 	enabled
IPv6 Support 	enabled
Registered PHP Streams 	php, file, http, ftp, compress.bzip2, compress.zlib, https, ftps
Registered Stream Socket Transports 	tcp, udp, unix, udg, ssl, sslv3, sslv2, tls
Registered Stream Filters 	string.rot13, string.toupper, string.tolower, string.strip_tags, convert.*, consumed, convert.iconv.*, bzip2.*, zlib.*

My non-phpinfo output looks like this:

<br />

string(20) "foo isn't<br />
 bar"

Two notes:
a) Yours lacks the first <br />
b) Our strings are both length 20, yours should say 18

What do you think of this? Almost as if there is something changing your code after PHP... 

Sorry I forgot to copy the first <br>


I think I'm losing my mind - I just did the exact same test, and now I'm getting the correct 

<br />

string(20) "foo isn't<br />
 bar"

I'm speechless... nothing was changed, and the server wasn't restarted.

Maybe this should be closed - damn gremlins!

Maybe an old php binary is hiding on the server somewhere... or the gremlins, they are always possible too :)