I think I fixed it!
It was actually an internal, valve problem.
Ports and the server was doing fine, it was the actual server code that is borked up.
Anyone else who has this issue, add these lines to your config:
setmaster remove hl2master.steampowered.com:27011
setmaster remove hl2master.steampowered.com:27015
setmaster add hl2master.steampowered.com:27011
setmaster add hl2master.steampowered.com:27015
Since the uber update, they messed up the code. So you have to force the master servers to see and report your server properly by putting it in legacy in mode.
Thanks for all the help, and I will start spreading this fix around!
Also make sure you disable replays- it has been found that replays will mess things up as well.