s
  Treat string as single line. That is, change ``.''
  to match any character whatsoever, 
  even a newline, which normally it would not match.

##</code><code>##

use strict;
use warnings 'all';

my @lines = (
 	"two three two twoone\ntwo four", 
	"four five"
);

my $old_hostname = 'two';
my $new_hostname = 'one';
my $new_file = 'filename.txt';

open(FH,'>',$new_file) || die $!;
foreach my $line (@lines) 
{ 
	$line =~ s/(.*?)$old_hostname(.*?)/$1$new_hostname$2/sgi;
	print FH $line . "\n";
}
close(FH);

##</code><code>##

one three one oneone
one four
four five