An ultimatum is a threat and an attempt to assert power; you really can't directly issue a threat from a position of weakness (regardless of whether you intend to carry it out or not) without coming across as petulant or idiotic. As an aside, ultimatums from a position of strength are a completely different animal.
The correct way to handle this is a little more diplomatic than going around and proclaiming "if I don't get my way, I'm going home". For one, if you issue that ultimatum you have to be prepared to follow through on it no matter the personal cost or risk losing all credibility in any future negotiations. For another, you're likely to trigger some negative emotions from your counter-party, which is a dangerous and unpredictable game.
You can't really influence your manager's decision about whether to move you immediately or not. Therefore, your only play here is to be sure that your manager understands the risk; ideally, you'd do that in such a way that you don't end up burning bridges or backing yourself in a corner. Once you know your manager understands the risk, then his actions tell you the next play - in this case, looks like the options are either stick it out or find a new job.
How you communicate this risk to your manager while maintaining some level of composure depends on your relationship until now. In my case, I generally don't bring things up to my management unless asked, or it's a serious problem I need help with. I can get away with saying something seemingly nonchalant and with a smile like "I don't know how much longer I can continue working with George" a few times and the message would be clear.
If I really wanted to emphasize it, a comment such as "George is stressing me out this week" would add a little more emphasis to the fact that I see George as a problem.
If I was feeling particularly bold and unsure that my message was being received, I may throw in a throwaway comment about a local firm that's hiring or a friend that started a new position such as "You remember Bob? I ran into him at the grocery store - he just started over at Acme Corp. Says it's been really good - maybe I should apply there! Ha ha!" (you have to do this as a joke; the point is to let them know you know the market and know you have options, not to threaten).
These seemingly throwaway comments and jokes are code for the following series of statements - but never made in an overtly threatening or unprofessional manner:
- I don't like George, and am unhappy working with him
- I know I can change it (so do you)
- I'm giving you a chance to change it first
- If you don't or can't then I will
At that point, a few different things can happen. Your manager is clueless and didn't receive the message. Your manager is aware of the risk, and chooses to do nothing about it. Or your manager actively works towards a resolution.
If your manager is clueless, you're kind of stuck. Assuming not everyone in your organization is clueless, you still can't issue an ultimatum. So you should either find a new job, and/or work towards replacing your manager.
If your manager is aware of the risk, and chooses to do nothing about it - then you have the answer to your ultimatum without ever having to issue one and living through the consequences. You don't have enough leverage to force a change; sounds like you need to polish off that resume. By avoiding the confrontation though, you can do it on your own timetable and with no ill feelings.
If your manager is actively working towards a resolution, then you get what you wanted without ill feelings. Your manager will appreciate your subtlety, and won't have to explain to his boss that he moved you because you were unhappy and complained (which, believe me, he doesn't want to do...because his boss would probably just fire you or plan for your replacement instead, because he doesn't want you having that power over his organization).