I don't see anything wrong with that at all... In fact, when I run it, I get the exact string you're wanting it to create.....

#!/usr/bin/perl -wT
use strict;

my $new_type = "BookInstructional MaterialTeaching Guide";
print "Before: $new_type\n";

$new_type =~ s/([a-z])([A-Z])/$1::$2/g;

print "After:  $new_type\n";

=OUTPUT
Before: BookInstructional MaterialTeaching Guide
After:  Book::Instructional Material::Teaching Guide
[download]

Update: The double colon is special in perl so if it really isn't working for you, I'd try to disambiguate /$1::$2/ using /${1}::${2}/ as in:

$new_type =~ s/([a-z])([A-Z])/${1}::${2}/g;
[download]

-Blake