Veggie: don’t forget to give some credits to your boss’s boss.

With your boss only being there for a month, I don't think you can get promoted without your boss’s boss support. When good thing is happening (like promotion, raise), people tend to say: it is me..it is me who did all these for you. When promotion didn’t go through, people would say:”oh, it is not me. I totally support you but someone had objection on this..” This “someone” could be the big boss, your boss’s colleague or could be anyone who don’t even know you, but who knows what really happened.