I have to agree with lidden, your benchmark is flawed.

1. The signal to noise ratio between the code being benchmarked and the code being tested is is so low as to obscure the real differences. subroutine calls are very expensive relative to the operations.
2. Both your tests are used in a void context and are possibly being optimised away.

If you put the tests into a boolean context, and loop the tests to negate the overhead of calling the subs, you consistantly get the boolean operation coming out faster than the modulo operation. Even for modest loop counts:

Perl> $loop = 1; $counter = 0; 
cmpthese -1, { 
    and=>sub{ for(1..$loop){ ++$counter & 1 and 1 } }, 
    mod=>sub{ for(1..$loop){ ++$counter % 2 and 1 } } 
};;
        Rate mod and
mod 517876/s  -- -2%
and 525790/s  2%  --

Perl> $loop = 10; $counter = 0; 
cmpthese -1, { 
    and=>sub{ for(1..$loop){ ++$counter & 1 and 1 } }, 
    mod=>sub{ for(1..$loop){ ++$counter % 2 and 1 } } 
};;
        Rate mod and
mod 229555/s  -- -7%
and 245513/s  7%  --

Perl> $loop = 100; $counter = 0; 
cmpthese -1, { 
    and=>sub{ for(1..$loop){ ++$counter & 1 and 1 } }, 
    mod=>sub{ for(1..$loop){ ++$counter % 2 and 1 } } 
};;
       Rate mod and
mod 35041/s  -- -6%
and 37118/s  6%  --

Perl> $loop = 1000; $counter = 0; 
cmpthese -1, { 
    and=>sub{ for(1..$loop){ ++$counter & 1 and 1 } }, 
    mod=>sub{ for(1..$loop){ ++$counter % 2 and 1 } } 
};;
      Rate mod and
mod 3641/s  -- -7%
and 3931/s  8%  --

Perl> $loop = 1000; $counter = 0; 
cmpthese -1, { 
    and=>sub{ for(1..$loop){ ++$counter & 1 and 1 } }, 
    mod=>sub{ for(1..$loop){ ++$counter % 2 and 1 } } 
};;
      Rate mod and
mod 3725/s  -- -7%
and 3989/s  7%  --
[download]

It's not huge, but it is consistant.