I'm out of ideas

[Halivar]

Hmm...OK I know this doesnt technically work by the RAW but how about:
Abysal paraillithid half-green dragon giant psion?

Depends. Are there feats available to give him extra tentacles?

 

[Jondor_Battlehammer]

Yes, in lords of madness there is a feat granting two tentacles as natural weapons. There is also a feat to add 5' reach to all your natural weapons as you gain extra joints in your limbs.

 

[Jürgen Hubert]

Let them fight a few of these humanoids. And from the loot they get, they should gain the impression that they might be savage and evil, but that they also have civilization of sorts - one that could give them clues.

Describe their jewelry or tatoos. Hint at their significance, and that they might perhaps represent those evil wizards in one of their guises. If they have encountered the symbols used by those wizards before, then these humanoids might use them in debased form. That allows the PCs to speculate that these beings might know something useful.

And then it's time for some field anthropology, D&D-style. They could sneak in invisibly and listen in to their conversations. They could capture some of them and interrogate them. They might even try some open negotiations with them. The main thing is that they are gaining information much faster than if they were just randomly wandering into the swamp.

 

[Dioltach]

Thinking along the lines of the Black/Green Dragon conflict: if, as suggested above, the evil wizards have driven off one of the dragons because its lair was too close to their base, it would be logical that it's now vying with the other dragon for territory.

I like the idea of the wizard's base moving: a floating island! (Not to mention locating it in the middle of an ever-shifting series of waterways, caused by clumps of reeds/mud/whatever floating around.)

Another consideration is that in a huge area that has one type of environment, the animals/monsters will tend to grow bigger and bigger (as a previous poster mentioned, more HD).

 

[Dannyalcatraz]

Another consideration is that in a huge area that has one type of environment, the animals/monsters will tend to grow bigger and bigger (as a previous poster mentioned, more HD).

Especially if they have a caretaker...like a Druid who loves the swamplands.