I wonder, could it have something to do with loop-including ?

Circular dependencies don't automatically cause a problem, it also depends on what the module does in its body (which you haven't shown). If you think there is a problem, a short piece of example code that reproduces the problem would help, see http://sscce.org/

But first, did you try what choroba suggested?

I did try what choroba suggested, and it didn't work.
I've put together three small files, for demonstration purposes:

Foo.pm

# Test module foo

package Foo;

use Bar;
#use Bar qw(BarFunc BarSub);

BEGIN {
    require Exporter;

    # set the version for version checking
    our $VERSION = 1.00;

    # Inherit from Exporter to export functions and variables
    our @ISA = qw(Exporter);

    # Functions and variables which are exported by default
    our @EXPORT = qw(FooFunc FooSub);

    # Functions and variables which can be optionally exported
    our @EXPORT_OK = qw();
}

sub FooFunc {
    return 'I am the FooFunc !';
}

sub FooSub {
    return 'FooSub reporting in !';
}

1;
[download]

Bar.pm

# Test module foo

package Bar;

use Foo;
#use Foo qw(FooFunc FooSub);

BEGIN {
    require Exporter;

    # set the version for version checking
    our $VERSION = 1.00;

    # Inherit from Exporter to export functions and variables
    our @ISA = qw(Exporter);

    # Functions and variables which are exported by default
    our @EXPORT = qw(BarFunc BarSub);

    # Functions and variables which can be optionally exported
    our @EXPORT_OK = qw();
}

sub BarFunc {
    return "I, BarFunc, solemnly declare: ".FooFunc()."\n";
}

sub BarSub {
    print "Howdy, Stranger !\n";
    print "I'm BarSub, and I'm going to tell you a secret: '".FooSub()
+."'\n";
}

1;
[download]

perlTest.pl

use Foo;
use Bar;

print FooFunc()."\n";

BarSub();
[download]

Now, when I run the command: perl perlTest.pl, I get the following output:

I am the FooFunc !
Howdy, Stranger !
Undefined subroutine &Bar::FooSub called at Bar.pm line 30.
[download]

Is the problem clearer now ?

EDIT:
Also, if I comment out the "use Foo;" and "use Bar;" lines from the modules, and uncomment the longer use lines (the ones with qw(...) on them), I get exactly the same output.

Having both modules use each other, combined with BEGIN trickery is prone to subtle errors.

I would restructure your modules to avoid that. Either put the common routines into a third module or reconstruct your modules so you don't need to do the BEGIN trickery.

Corion is right, and you will be happier in the long run if you follow that advice. I just wanted to note that if I move your use Foo; / use Bar; statements after the respective BEGIN blocks, your example code works for me. I'm guessing it could also be some interaction with Exporter (but I haven't yet bothered to track it down exactly). Or, changing the calls to the functions to use the fully qualified names (Foo::...) works too.