OK
So I've figured out the problem.

First of all if you use the NavigateURL property when binding the data
to the Treeview it will not raise the OnSelectedNodeChanged event.
That's part 1 of the problem. Since I am using a master page with the
treeview on it each time a user selects a different node it redirects
them to a different page and therefore loads the master page again and
looses the viewstate of the treeview.

So to combat this I took out the NavigateURL property for each node and
instead performed a Response.Redirect within the OnSelectedNodeChanged.
The main issue in this is that the client wanted to see the selected
node highlighted and of course with the issue I am having where the
treeview looses its state it cannot highlight the selected node because
it is being reloaded the whole time.

So what I done inside the OnSelectedNodeChanged Event (It gets raised
now because the NavigateURL property is not present) is created a
session variable "SelectedNodeValuePath" and set it equal to the
Treeview.SelectedNode.ValuePath property. Then OnPagePreRender within
the master page I set the selected node to
TreeView.FindNode(Session["SelectedNodeValuePath"].ToString()).Select().

This solves my problem, except that the value for each node is infact a
url which contains "/" characters. This was causing all sorts of
problems for the FindNode method. Seems that the "/" character is the
default delimiter for the Treeview valuepath fields. So what I had to do
as well was set the PathSeparator=":" on the Treeview and all worked.

Hope this helps someone and they don't have to waste any of their time.

Nikron