The problem with your code is due to the lack of strict and warnings. If you had those turned on you would see that your call to set the colour is wrong:

# $note->(Color) <--------wrong
$note->{Color} = $Color;
[download]

I tested it and was able to create a note of the colour blue just by changing that line :)
Update: heres some working code. I tested it on Outlook 2000 on win2k using Activestate Perl

use Win32::OLE;
use strict;
use warnings;

use constant    olBlue    =>    0;
use constant    olGreen    =>    1; 
use constant    olPink    =>    2;
use constant     olWhite    =>    4;
use constant    olYellow    =>    3;

use constant    olSave    =>    0;

my $options = {
    'Body'    =>    "Test note",
    'Color'    =>    olBlue,
    'Categories'    => "Favorites",
    'MessageClass'    => "IPM.StickyNote",
};

my $Outlook = Win32::OLE->GetActiveObject('Outlook.Application');

# Setup Creation of a new Note
my $note = $Outlook->CreateItem(5);
      
# Write Note Title & Body
while (my ($key,$val) = each %{$options})
{
    $note->{$key} = $val;
}

# Close and Save note.
$note->Close(olSave);
[download]