I switched from ActivePerl to Strawberry Perl too; although I'm using different perl versions to you. Here's my Windows Path:

C:\strawberry\c\bin;C:\strawberry\c\i686-w64-mingw32\bin;C:\strawberry
+\perl\site\bin;C:\strawberry\perl\bin;C:\Perl\site\bin;C:\Perl\bin;<o
+ther non-perl stuff here>
[download]

So that's Strawberry (C:\strawberry\*) at the very beginning; ActivePerl (C:\Perl\*) next; other Windows paths at the end.

I have *.pl files associated with Strawberry perl. Perhaps you need to do that.

I also start all my scripts with the shebang line:

I have the additional complication of also running Cygwin. That shebang line lets me run one script from either environment without having to do anything special (although I'm not sure if it's actually read under Windows). In case you're interested, I'm running 5.12.0 in both.

The Strawberry Perl site has some information about relocating Perl: "Now you can tell Strawberry Perl 5.12.0 where YOU want it to go: 64-bit machines, odd directory locations, USB sticks, etcetera.". I haven't used it and don't know if it pertains to your version; however, if you're still having difficulties, it might be of some help.

Update: Re your ftype and assoc commands above, I get:

C:\_\tmp>ftype Perl
Perl="C:\strawberry\perl\bin\perl.exe" "%1" %*

C:\_\tmp>assoc .pl
.pl=Perl

C:\_\tmp>
[download]