I do note that if I boot with the phone connected, it works without me having to do the above.

but it still doesn't actually work - ie still a routing problem or something like that.

Aha! I have shorewall installed and running. If I /etc/init.d/shorewall stop, then it works

Awesome.

So, all I need to do is have the phone booted when I boot my computer and it'll work just fine

Good enough...

Max.