BETWEEN in a SELECT is slow.

I’m using SQL Server 2000 and a BETWEEN in the WHERE clause.
My basic query is:
SELECT * FROM mytable WHERE 3507184416 between RangeLow AND RangeHigh

There is a clustered index on RangeLow and a nonclustered index on RangeHigh.
Both fields are BigInt and there are about 7 million records in the table.
A query like the following will complete immediately. .
SELECT MAX(RangeLow) from  mytable where RangeLow <= 3507184416
If I use between it takes about 4.5 minutes.
Anyone know what I should be doing for this to work properly?

TIA,
Chris