The issue seems to be fixed as of Version 10.1.
Just came across the strangest bug under both Mathematica 9.0.0 and 9.0.1. If one enters:
Solve[m == p Sin[x] && -Pi/2 < x < Pi/2, x]
... then Mathematica whirrs and whirrs (running on my Mac Pro with OS X 10.6.8), and doesn't seem to produce any answer (I gave up after a few minutes). But if one changes symbol p to something that 'sorts' earlier than an m, such as an 'a' or 'b', then it works correctly:
Solve[m == b Sin[x] && -Pi/2 < x < Pi/2, x]
Solve::nsmet: This system cannot be solved with the methods available to Solve.
Obviously, one can add assumptions on p or b to make it solve, but that is not the issue being raised.
Is this just a Mac issue, or are others experiencing the same on other platforms?