Date::Manip is, as far as I know, the only one that does this. I think this has come up before so you should Super Search it too. Here's a snippet I use from the command line. Read the docs to see what's going on.

use Date::Manip;

my $str_date = shift || die "give a date!\n";  # almost *any* format

$str_date = 
    $str_date =~ /^(?!19|20)\d{7,10}$/ ?
    ParseDateString("epoch $str_date") : $str_date;

print UnixDate( ParseDate( $str_date ), "\t%D %X, %A\n");
[download]

It gets all your examples but one.

jinx@jasper[38]~/bin>dater "22 Oct, 15:30"
    10/22/04 15:30:00, Friday
jinx@jasper[39]~/bin>dater "noon tomorrow"
    10/22/04 12:00:00, Friday
jinx@jasper[40]~/bin>dater "this afternoon at 3"
jinx@jasper[41]~/bin>dater "this afternoon"
jinx@jasper[42]~/bin>dater "this afternoon at 3"
jinx@jasper[43]~/bin>dater "today at 3"
jinx@jasper[44]~/bin>dater "today at 3pm"
    10/21/04 15:00:00, Thursday
jinx@jasper[45]~/bin>dater "10am next tuesday"
    10/26/04 10:00:00, Tuesday
[download]