You need to look at perl re, specifically the s modifier:

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

I've taken your code and thrown a quick example together. This code isn't anything special but it works and hopefully will point you in the right direction

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);
[download]

Which outputs:

one three one oneone
one four
four five
[download]

If you need to delimit the occurences more tightly then you'll need to modify the (.*?) constructs :).

Please msg me if there are any fubars :)

HTH

Simon