Yeah, your datastructure is definitely a problem.
A common, and very fast way, let the nodes be cells in an array, like pixels in a bitmap, and just mark cells as "unpassable" for walls and such.
Then finding neighbours is as easy as adding or substracting to the index of the current node.
Edit: didn't see the last post Glad to see you've improved it.
yeah the flagged 'grid' border eliminates the costly edge coordinate tests
I helped someone long ago with every optimzation possible and even went so far as ditching the 2D array, using a single dimensional array/memory block and pointer math +/- 1 for the X axiz and +/- a precaclulated map width for the Y (I forget if we did byte addressing directly to get rid of the pointer multiply altogether- though I do recall an 8 grid direction array with all the single value offsets precalculated) .
The pointers also helped with the open/closed list (one offset value to point to the map data) . Along with other things like using a HeapQ and smallest datas possible to minimize cache misses (which was far more significant than word alignment issues).
It was amazing how much faster we got it to run (and we were using large maps 1K x 1K where you needed the performance)