I needed to solve a similar problem: pathfinding on a large maze-like grid with constantly changing "costs" and barriers.
The thing is, in tower defense game the number of entities that need to have the path solved for them is usually much larger than the number of nodes in the graph. A* is not the most appropriate algorithm for handling this, because you'll need to solve it anew each time something is changed. Well it is appropriate if you need to find only one path, but in my case I needed to be able to handle entities which can appear in different locations and each has its own path.
The Floyd-Warshall algorithm is far more appropriate, though for my case I wrote a custom algorithm that whenever a node changes, it re-calculates the cost to that node from all its neighbors, and then if the neighbors have been changed it is invoked recursively on them.
So in the beginning of the game, I just fire up this algorithm on all my "goal" nodes. Then, whenever a single node changes (for example, becomes un-passable), I just fire it up on that node and the change is propagated to all the nodes that will be affected, and then stopped. So no need for global recalculation, and the algorithm is completely independent from the number of entities that will require pathfinding.
My algorithm was basically something like (pseudo-code):
update_node method in Node class:
$old <- $my_score
find $neighbor node among all neighbors such that
$neighbor.score + distance_to($neighbor) is minimal
$my_score <- $neighbor.score + distance_to($neighbor)
$next_node <- $neighbor
if ($my_score != $old)
for each $neighbor
With the initial score depending on whether the node is a target or some kind of barrier.