How soon following the arrival of a new boss is it appropriate to discuss a pay raise/changing pay grades? Last spring my boss was fired, prior to her firing we were in the process of moving me up a pay grade in my company. The move is one that is appropriate in view of my time in the position and my demonstrated results. During the transition period her boss (who I have a relationship with) assumed the responsibiliites on an interim basis. During the transition all of us had individual meetings with the iterim boss and were invited to rasie concerns about our department, and to discuss any concerns or impacts of the firing. I took this as an opportunity to let the iterim boss know that we were in the process of evaluating moving my pay grade and I was concerned that any work that was done in that regard could be lost. The iterim boss stated he supported the move, and would pass on his support to the new full time boss when the next opportunity arose to move me up a pay grade. The new boss arrived two weeks ago and reports into the man who served as the iterim boss. The window of opportunity to move me up a pay grade will open back up in about 6 weeks. Is it appropriate to bring up this issue with my new boss already? I recently had a high profile success resolving an issue, but in two weeks it is impossible to establish a track record of delivering results. I have thought about contacting his boss and reminding him of our discussion, but I don't want to be viewed as going over the new boss. Am I stuck and should I just wait another 6 months? The next pay grade jump represents a pretty big pay increase (15-17%) and I am understandably looking forward to making the move.

Very tricky
That does seem to be a tricky situation, you really don't want to be the person who pounces on the new boss asking for more money. Although I understand why you want to.
I am not sure as to the best answer at all. In order of preference I would think the following, although I suspect if it were me I would take option 2.
1 - Wait - You don't risk your good will, but are reliant on them to do the right thing
2 - Approach boss's boss - If you have a good relationship, you could present it exactly as you have here and I think it should be well received
3 - Ask new boss
--
Chief Executive, Connect Support Services Ltd. - London based cloud & traditional IT services for SMEs
http://uk.linkedin.com/in/markodell100 - https://twitter.com/mark_odell
Cast for that?
There was a podcast a couple of years ago that talked about what to do in a boss transition. It included writing a transition packet that included summaries regarding your position, what projects you're on, key relationships and various "in-progress" things, including things discussed in O3s. That was then given to the former boss to give to the new one, with a copy kept in-case the packet doesn't make to the new boss.
I'd say it'd be appropriate to put a line-item in that packet regarding the in-progress pay-grade discussion. That said, I'd not highlight it, or push to hard, just include it in the packet.
I'd most definitely not bring up the issue by itself unless asked about it.
Wait...
"The iterim boss stated he supported the move, and would pass on his support to the new full time boss when the next opportunity arose to move me up a pay grade."
It looks like your boss' boss knows your contributions to the company, thinks you are doing a good enough job to be promoted, and supports your promotion.
I'd hang tight and wait and see what happens through the first eligibility window these first six weeks. If this doesn't work out, you might want to take a more direct approach during your next review or performance discussion.