This might be a stupid (tm) question, but did you try replacing the double-colons with dashes?

This is what I get on my (win32) box:

K:\Temp>ppm search File::Find::Rule
Searching in Active Repositories
No matches for 'File::Find::Rule'; see 'help search'.

K:\Temp>ppm search File-Find-Rule
Searching in Active Repositories
   1. File-Find-Rule                 [0.28] File-Find-Rule
   2. File-Find-Rule-Digest          [0.01] File-Find-Rule-Digest
   3. File-Find-Rule-DIZ             [0.05] File-Find-Rule-DIZ
   4. File-Find-Rule-Filesys-Virtual [1.21] File-Find-Rule-Filesys-Vir
+tual
   5. File-Find-Rule-ImageSize       [0.03] File-Find-Rule-ImageSize
   6. File-Find-Rule-MMagic          [0.02] File-Find-Rule-MMagic
   7. File-Find-Rule-MP3Info         [0.01] File-Find-Rule-MP3Info
   8. File-Find-Rule-SAUCE           [0.02] File-Find-Rule-SAUCE
   9. File-Find-Rule-Type            [0.05] File-Find-Rule-Type
  10. File-Find-Rule-WellFormed      [0.01] File-Find-Rule-WellFormed
  11. Test-File-Find-Rule            [1.00] Test-File-Find-Rule
[download]

Cheers,
Darren :)