I would assume that one of said complications would be the fluctuating nature of "price" as data in the search equation, especially considering RightStuf's penchant for sales bargains.
There's a number of different prices that we sell items for, with the easiest examples being how we sell our own label's items to other retailers, or the daily deals and weekly specials. The index that we're using right now to drive the new search is an item-centric search, coming off a view of the information that is aware of all the different pricing but doesn't know what the lowest store price is.
To sort by the "lowest available price in the store from all possible prices" is something we don't have indexed right now, and it required a more store-centric view of the items.
It's a weird point-of-view thing for the data issue, and I probably explained it poorly here, but it is high on the list of things I want to offer. We have a lot of pretty awesome (IMHO) search enhancements coming. What we have out now was really just laying the foundation for them.