My guess would be that since there are only ~150 players playing Spartan Ops at one time, it is actually taking you 15-30 minutes to find a game (especially since your NAT is set to open).
In my own experience (similar to RandomDisplayName in the comments), trying to join any kind of matchmaking with so few players online will take some time. I tried replaying some COD: MW2 free-for-all recently with ~500 people online, and it took around 15 minutes to connect to a game.
My only advice would be to try to play during times when there are more people online (in my experience this is usually weekday evenings and weekends). With more players online hopefully your waiting time will decrease.