If I modifiy your code so that it is stand alone and doesn't require external applications then I don't see the problem you describe. Can you modify this code to reproduce the error (without introducing external dependencies)?

use strict;
use warnings;

my @times;
my $timeDisplay;
my $timeMinute = '56';
my $timeHour = '34';

while(my $line = <DATA>) {
    chomp $line;
    unshift(@times, $line);
}

$timeDisplay = join (":", "$timeHour", "$timeMinute");
unshift(@times, $timeDisplay); #puts in new time to queue

foreach my $i (@times) { #prints back into fileTimes to update
print "$i\n";
}

__DATA__
12:34
56:78
[download]

Prints:

34:56
56:78
12:34
[download]

My guess is that your external application (date) is returning newlines at the end of its string. You might want to take a look at some of the Perl date and time handling functions (time, gmtime and localtime) and modules (Date::EzDate and many others) rather than calling an external application.