It was a calculation error, instead of using tan I was using atan
But I think my solution is flawed. Lets ignore the above example and work with this one. Both heading and elevation is 0°, this makes my box's dimensions 1213, 21, 623. I'm choosing to fit the box horizontally. The opposite side is half x (606.5) and my half FOV is 52.5° (from the calculated horizontal FOV of 105°). distance = opposite / tan(halfFOV) = 465.
Now the math is right but the fustrum is too small and part of the cube is outside of it.
I found out what my problem is. I'm calculating how far FROM THE ORIGIN the camera needs to be to fit something so wide/tall in it's frustum, I forgot to acount for the box's width/height (well, half width / half height).