The code looks alright, i'm going to assume it works, i don't code in XNA, so i don't know which objects are yours. The issue is that you're not checking which collision resolution is the smallest. If either x or y velocity is 0 then
if(Math.Round(velocity.X) != 0.0f) {
HandleCollisions2(Direction.Horizontal);
}
if(Math.Round(velocity.Y) != 0.0f) {
HandleCollisions2(Direction.Vertical);
}
is going to sort it for you (since there's possible collision only along the vertical or horizontal axis). However, if both of those velocities are different than zero then the collision is going to get solved for the horizontal axis first, then there won't be any collision so the vertical collision handler never gets called.
If you want to fix this, check both vertical and horizontal collision and find the smallest displacement vector, then resolve collision. If you want to do what David explained then you'll need to do some more checking, but the general issue i explained still stands.