Recursive uniform cost search that needs to be optimized
Unpack your tuple to improve readability. There's already a comment 

# Each tuple is: (actualScore, minScore, previous, totalScore, y, x)


Put those names in code like this so you can use eg. actualScore instead of m[0]:

(actualScore, minScore, previous, totalScore, y, x) = m

You are using recursion to implement a simple loop. I get RuntimeError: maximum recursion depth exceeded even from problem 18. That's because you recurse from every node on every path until you find a solution. Just use a while loop instead.
Use the heapq module to implement a priority queue to avoid the linear search done by min.
Compare numbers using ==. Only use is for object identity.





To learn about the A* algorithm, see the highly readable tutorial at Amit’s A* Pages.
You'll notice that your approach is different. In particular, you don't compute a heuristic. On the other hand I'm not sure if a useful heuristic exists for this problem, but in any case your approach is more like Dijkstra'a algorithm.
You should keep track of already visited nodes to avoid exploring the same multiple times.
When you add nodes to the priority queue, you should already compute their scores. Now you add both children with the score of the parent. When you eventually pop these nodes from the queue, you get the left child even though you need the better one first. Try the small example at the top of the problem 18 page: program answers 19 instead of 23, because at the bottom row the 5 pops from the queue before the 9.