Is the network at the top of the list of preferred networks? I've found similar problems if a network is not in the past. Another fix for similar problem has in the past be to enable AppleTalk for the network. Doesn't make much sense to me but it has proven to work before.