Hi Scott,
Will probably need some more information to trouble shoot this:
1. What RDBMS are you using? (i.e. SQL Server, Oracle)
2. What version is your geodatabase? (i.e 10.3)
3. What geometry is your feature class stored in? (i.e. ST_GEOMETRY, GEOMETRY, SDE_BINARY)
4. Does the feature class have a spatial index?