Hello Nick,
This is because you are not using the index that you have created. You have to add a label to your nodes that you matching to use the index. Otherwise, your query will perform a AllNodesScan which is very bad for performance.
MATCH (m:Label {User_ID: '1000'})-[r]-(n:Label {User_ID: '1232'})
RETURN m,n,r
You should take a look at query tuning using this documentation for starters
Hope this helps 