In order to use AITools pathfinding on maps with a large number of nodes, you'll need to break the map into subsectors. If you can, reducing the number of nodes, like yoplalala suggests, would probably be the simplest approach. If that idea complicates some other part of your project, you could still search a large area using the subsector approach. You may remember my description of this idea (here:
http://community.stencyl.com/index.php/index.php?topic=41034.msg301147#msg301147).
The maps in
Towers of Vallas are 80 x 80 x 4 nodes, which is about an order of magnitude smaller than your maps--but the approach could still work. The basic idea is that you break the map into subsectors (say, 32 x 32 pixels). Create a "main graph" that records which subsectors are connected to each other. Each subsector has its own graph that determines which walkable pixels are connected, and can get the player either to the next subsector, or the target if the player is in the same subsector as the target.
You could also have subsectors and break those into even smaller subsubsectors. In theory, I think you can remove CPU usage as a bottleneck in searching graphs--although my experience managing subdivisions wasn't a pleasant one

The graph searching aspect worked great, but I had all kinds of other issues (namely, rendering) with subsectors.