1) What optimisation options did you use?

2) Which compiler did you use?
The gcc 4.0 and 4.1 Fortran compilers for instance are still pretty
much in their infancy, so one would expect bugs and strange behaviour
there. Use 4.2 or 4.3 instead, if you use gfortran.

3) How did you measure execution time?
I find that accuarate timing on a computer is a nontrivial task. The
'time' command on my machine shows up to 200% variance. I can only
assume you used some clever and appropriately precise way of
measuring.

I'm not a compiler specialist but AFAIK, array operations should not
usually be slower than explicit loop constructs.

Why? When using array operations like -say- x = MATMUL(A,b) in
contrast to two nested DO-loops, the compiler has a greater amount of
information at hand about what it is you want to do, which allows it
to use more aggressive optimisation methods to generate code, or to
generate calls to (more or less optimised) runtime libraries; the
latter is done by all compilers I know.
Additionally, the gfortran compiler has the '-fexternal-blas' option
which tells the compiler to automagically generate calls to an
optimised vendor BLAS for certain array operations, instead of using
the runtime library. I've never tried this, but using a tuned ATLAS
library will surely speed things up nicely.

A second benefit of array operations is their conciseness. Take the
MATMUL example again: A single call opposed to two nested DO-loops. Or
think of copying part of an array into another array, anything really!
IMHO, a lot of scientific code completely disregards maintainability
issues for the sake of the highest possible degree of code
optimisation.
Using array operations makes your code more concise, more readable and
therefore easier to maintain in the long run! It *should* also
improve, or at least not hurt, performance.