Yes, you may have both, however, your contribution to a regular IRA may not be deductible or partially deductible depending on your adjusted gross income level and whether you are considered to be an active participant.
For a defined contribution plan such as a 401(k) the Congress has defined an active particpant as; "an individual is an active participant in a defined contribution plan if employer contributions, employee contributions or forfeitures are allocated to the individual's account with respect to a plan year ending with or within the individual's taxable year. The rule applies even if the individual is not employed at any time during the taxable year."
Accordingly, the focus in testing for active participant status under a defined contribution plan is upon whether your account actually has received an allocation of contributions with respect to a plan year, rather than upon the your mere eligibility to accrue a benefit, as is the focus for defined benefit plans. Thus, an individual who elects not to participate in a defined contribution plan (i.e. a 401(k) should not be considered an active participant, unless the Company makes a contribution to your account for you.
If you are an active participant you may deduct contributions if your AGI is below certain limits depending on your filing status. For 2005 deductible IRA contributions phase out for singles with AGI between $50,000 and $60,000. For MFJ phase out is between $70,000 and $80,000. For MFS the phase out range is $0 to $10,000. Roth IRA contributions phaseout between $95,000 and $110,000 for singles and $150,000-$160,000 for MFJ. For MFS its still between $0 and $10,000.
So the bottom line in your situation is that if you elect not to participate in the 401(k) and the Company does not contribute to your account for that tax year, then you will not be an "active participant" for that tax year. Accordingly, you would not be subject to the AGI limitations for that tax year. One side note. If the Company has a defined benefit plan which will accrue a benefit for you whether you elect to participate or not and whether your benefit is vested or not, you will be an active participant.
Because it is impossible for me to identify and consider ALL the relevant facts, this advice is not intended or written to be used for the purpose of avoiding penalties, and cannot be used for that purpose.