Arrow's theorem is a classical theorem. Finding an open problem is not easy for social choice theorists (or at least for me), either.
My general advice to students studying economics is: "stay way from the theorem, unless you can relate your contribution to some recent ideas (e.g., axioms that has been proposed recently, solutions that has been studied a bit, and behavioral assumptions in fashion). Try to find a problem unrelated to Arrow's theorem. There are many such problems even within social choice theory." Only after you have a general idea what sort of problem you want to pursue, check the Handbook of Social Choice and Welfare.
Computational issues could be one of such "recent" ideas. Though the investigation of complexity (of the rules or of manipulation or of the solution, etc.) is the main concern for computer scientists (as suggested by others), there do exit papers (such as Mihara, 1997, Arrow's Theorem and Turing Computability, Economic Theory 10:257-276) that studies the (fundamental?) problem of computability within Arrow's framework. ;-)
Let me comment on the two problems you suggested.
I'm not sure if social choice theorists neglected to consider partial orders. If they did, they did so probably because "partiality" can be expressed by strict preferences (as we do in Kumabe and Mihara, Preference aggregation theory without acyclicity: The core without majority dissatisfaction, Games and Economic Behavior, in press). (In that case, better forget the weak preference R or define it differently [so it will not become complete]: By defining xRy [x is weakly preferred to y] iff not yPx [not y is preferred to x], we have P is asymmetric iff R is complete!)
Some authors are not, but I guess most social choice theorists are careful enough not to claim that any dictatorial social welfare function satisfy IIA. For example, I say (Mihara, 1997) that within the social welfare functions satisfying IIA, a rule is dictatorial iff it satisfies a certain condition. So they knew the problem was open, but were probably not interested in further classifying dictatorial functions. (Maybe Mossel and Tamuz can comment on Armstrong's errata cited by Mihara. It identifies a sequence of dictators or ultrafilters.) This suggests another research strategy (which I cannot recommend): try to find a problem that was uninteresting to social choice theorists.