First off, high five on the paycheck. There are a few retirement issues to deal with.
401k issues - At that income level, you will probably fall into the "Highly Compensated Employee" category, which means things get a little more complicated, both for you and your employer. (Wikipedia link)
IRA issues - As you already realized, you make too much to directly open and contribute to a Roth IRA. You can open a Traditional IRA, however. Your income is already over the limit for Traditional IRA deduction (bummer), so it would seem there is little point to opening an IRA at all.
However, there is a way to take advantage of a Roth IRA, even at your income level. It is possible to convert a Traditional IRA into a Roth IRA. There used to be income limits on the ability to do the conversion, which would have normally made this off limits to you. Starting in 2010, the income limit is removed, so you can do this.
Basically, you open a Traditional IRA, max it out, then convert it to a Roth. Since there was no income deduction, you shouldn't have to pay any more taxes. (link)
Disclaimer: I've never tried this, nor do I know anyone who has, so you might want to research it a bit more before you try it yourself.