You could try converting it from a recursive function to an iterative function that uses an array instead of the program stack.
Here's an iterative implementation of FloodFill as described in the article Allan mentioned:
function floodFill(bmpData:BitmapData, startX:int, startY:int, fill:uint, old:uint):void
{
var queue:Array = new Array();
queue.push(new Point(startX, startY));
var iterations:uint = 0;
var bmpWidth:int = bmpData.width;
var bmpHeight:int = bmpData.height;
var searchBmp:BitmapData = new BitmapData(bmpData.width, bmpData.height);
var currPoint:Point, newPoint:Point;
while (queue.length > 0)
{
currPoint = queue.shift();
++iterations;
if (currPoint.x < 0 || currPoint.x >= bmpWidth) continue;
if (currPoint.y < 0 || currPoint.y >= bmpHeight) continue;
searchBmp.setPixel(currPoint.x, currPoint.y, 0x00);
if (bmpData.getPixel(currPoint.x, currPoint.y) == old)
{
bmpData.setPixel(currPoint.x, currPoint.y, fill);
if (searchBmp.getPixel(currPoint.x + 1, currPoint.y) == 0xFFFFFF)
{
queue.push(new Point(currPoint.x + 1, currPoint.y));
}
if (searchBmp.getPixel(currPoint.x, currPoint.y + 1) == 0xFFFFFF)
{
queue.push(new Point(currPoint.x, currPoint.y + 1));
}
if (searchBmp.getPixel(currPoint.x - 1, currPoint.y) == 0xFFFFFF)
{
queue.push(new Point(currPoint.x - 1, currPoint.y));
}
if (searchBmp.getPixel(currPoint.x, currPoint.y - 1) == 0xFFFFFF)
{
queue.push(new Point(currPoint.x, currPoint.y - 1));
}
}
}
trace("iterations: " + iterations);
}
Edit: After trying a couple of ways to keep track of which pixels have already been searched, I realized that using a second BitmapData instance works really well. I've updated the code accordingly.
This code fills a 2000x1400 bitmap in ~14 seconds on my computer. For a better user experience, you should break up the fill processing over multiple frames, so the user doesn't have to stare at a waiting icon.
Oh, and this still only affects one color, but it should be easy to modify it to take multiple colors, or a color threshold, or similar.
Edit to add: The Flood fill article on Wikipedia has several algorithm suggestions.