Help w/speeding up range queries?

Hello-

#I am a biologist, and work with large datasets (tables with millions of
rows are common).
#These datasets often can be simplified as features with a name, and a
start and end position (ie: a range along a number line. GeneX is on
some chromosome from position 10->40)

I store these features in tables that generally have the form:

SIMPLE_TABLE:
FeatureID(PrimaryKey) -- FeatureName(varchar) --
FeatureChromosomeName(varchar) -- StartPosition(int) -- EndPosition(int)

My problem is, I often need to execute searches of tables like these
which find "All features within a range".
Ie: select FeatureID from SIMPLE_TABLE where FeatureChromosomeName like
'chrX' and StartPosition > 1000500 and EndPosition < 2000000;

This kind of query is VERY slow, and I've tried tinkering with indexes
to speed it up, but with little success.
Indexes on Chromosome help a little, but it I can't think of a way to
avoid full table scans for each of the position range queries.

Any advice on how I might be able to improve this situation would be
very helpful.

Thanks!
John