The VBA macro shows Type:=xlCellValue ; in your perl code, you instead have Type => "xlCellValue". The string "xlCellValue" is not the same as the constant xlCellValue

To gain access to the xl* family of constants, Win32::OLE::Const allows you to

use Win32::OLE::Const 'Microsoft Excel';
[download]

To use those constants in your call, you need to run

$rangeFormat->FormatConditions->Add({Type=>xlCellValue, Operator=>xlNo
+tEqual, Formula1=>"=TRUE"})
[download]

When I made those two changes to your code, I was able to see conditional formatting in the spreadsheet your code created.