It seems the filehandle must be opened for writing, on AIX.  This works for me (tested on AIX 5.1, 5.3 and 6.1, with Perl 5.8.2 and 5.8.4):

use strict;
use warnings;
use Fcntl qw(LOCK_EX LOCK_NB);

open DATA, ">>", $0 or die $!;

flock DATA, LOCK_EX | LOCK_NB or die "already running\n";

print "started $$\n";
sleep 300;
__DATA__
[download]

For example

$ ./761299.pl
started 1220690
^Z
Suspended
$ bg
[1]    ./761299.pl &
$ ./761299.pl
already running
$ kill 1220690
[1]    Terminated                    ./761299.pl
$ ./761299.pl
started 1220692
[download]

truss shows:

kfcntl(3, F_SETLK, 0x2FF22430)   = 0              # when not already r
+unning

kfcntl(3, F_SETLK, 0x2FF22430)   Err#13 EACCES    # otherwise
[download]

(instead of __DATA__, you can of course also open SELF, or whatever)

Update: replaced open DATA, ">>", "/dev/null" with open DATA, ">>", $0  (with more than one program, you'd use the same file, otherwise)

A problem with this approach would be that the program couldn't be installed on/run from a read-only file system...