Actually some of the links are nofollowed until it hits a karma threshold. Not sure of the value but it seems that a story with >50 votes is not currently nofollowed.
There's a disenfranchisement heuristic that causes your votes to be recorded (can't vote again) but not counted. It usually persists for about a day. I think it's supposed to kill voting rings but its behavior is pretty odd.
The number in your browser gets incremented or decremented client-side independently of reality — it's doing a blind GET request by pre-fetching an 'image', not making an XHR POST and getting the new karma value in the response. Like a lot of things in Arc, it's just poor HTTP.
edit: Oh wait, seems that only comment links are nofollow'd.