output.txt

array(3) {
  ["subject"]=>
  string(47) "Normal text www.foo.com
Normal text on new line"
  ["result"]=>
  string(80) "Normal text <a href="http://www.foo.com">www.foo.com</a> Normal text on new line"
  ["expected"]=>
  string(80) "Normal text <a href="http://www.foo.com">www.foo.com</a>
Normal text on new line"
}
array(3) {
  ["subject"]=>
  string(48) "Normal text www.foo.com 
Normal text on new line"
  ["result"]=>
  string(81) "Normal text <a href="http://www.foo.com">www.foo.com</a> 
Normal text on new line"
  ["expected"]=>
  string(81) "Normal text <a href="http://www.foo.com">www.foo.com</a> 
Normal text on new line"
}

regex.php

<?php

$pattern  = '/((https?:\/\/|www\.)[^\n\s]+)(\n|\s|$)/';
$callback = function ($matches) {
	if ($matches[2] == 'www.') {
		return sprintf('<a href="http://%s">%s</a> ', $matches[1], $matches[1]);
	}
	return sprintf('<a href="%s">%s</a> ', $matches[1], $matches[1]);
};
$subjects = array(
	"Normal text www.foo.com\nNormal text on new line"  => "Normal text <a href=\"http://www.foo.com\">www.foo.com</a>\nNormal text on new line",
	"Normal text www.foo.com \nNormal text on new line" => "Normal text <a href=\"http://www.foo.com\">www.foo.com</a> \nNormal text on new line"
);

foreach ($subjects as $subject => $expected) {
	$result = preg_replace_callback($pattern, $callback, $subject);
	var_dump(compact('subject', 'result', 'expected'));
}

Problem solved. :)

The (\n|\s|$) at the end was the problem, as pointed by @rdohms.