This is a duplicate of 6316090 and being closed.
As discussed in 6316090 Java makes no scheduling guarantees and applications should not be relying on any system provided notion of fairness. The changes in behaviour that have been observed are a side-effect of implementation changes to improve general throughput and performance. Additionally there are interactions with the underlying system scheduler that affect the observed behaviour.
In 1.5.0 the monitor queuing policy is "mostly prepend", which is essentially LIFO except that every N queue additions are done as an append rather than a prepend. Prepending yields better throughput/performance by trying to allow the most recently blocked thread to run next in the expectation that it will still have a warm cache etc. The occasional append prevents actual starvation, but the resulting behaviour can still be grossly "unfair" if expecting FIFO ordering.