http://i.imgur.com/1lB3t.png An example of the problem

CollisionWoes.cs

/// <summary>
/// Applies movement to the character based on input.
/// </summary>
/// <param name="gameTime">The current GameTime object.</param>
/// <param name="map">The current Map.</param>
private void ApplyMovement(GameTime gameTime, Map map)
{
    float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;

    velocity = movement * speed; // movement = unit vector, int speed = 225
    position += velocity * elapsed;

    HandleTileCollisions(map);
}

/// <summary>
/// Checks for collision.
/// </summary>
/// <param name="map">The current Map.</param>
private void HandleTileCollisions(Map map)
{
    // Get the bounding rectangle and find the neighbouring tiles.
    bounds = CollisionBounds;

    int leftTile = (int)Math.Floor((float)bounds.Left / map.TileWidth);
    int rightTile = (int)Math.Ceiling((float)bounds.Right / map.TileWidth) - 1;
    int topTile = (int)Math.Floor((float)bounds.Top / map.TileHeight);
    int bottomTile = (int)Math.Ceiling((float)bounds.Bottom / map.TileHeight) - 1;

    Vector2 depth = Vector2.Zero;
    Vector2 push = Vector2.Zero;
    Rectangle tileBounds = new Rectangle(0, 0, map.TileWidth, map.TileHeight);

    // Loop over each potentially colliding tile.
    for (int y = topTile; y <= bottomTile; y++)
    {
        for (int x = leftTile; x <= rightTile; x++)
        {
            // Get the collision type
            if (map.GetTileCollisionType(x, y) != CollisionType.Passable)
            {
                // Sets the position of the bounding rectangle for the tile
                tileBounds.X = x * map.TileWidth;
                tileBounds.Y = y * map.TileHeight;

                // If the player is colliding with the tile
                if (bounds.Intersects(tileBounds))
                {
                    // Get the depth
                    depth = bounds.GetIntersectionDepth(tileBounds);

                    if (Math.Abs(depth.X) > Math.Abs(push.X))
                        push.X = depth.X;

                    if (Math.Abs(depth.Y) > Math.Abs(push.Y))
                        push.Y = depth.Y;
                }
            }
        }
    }

    // If no collision was found, exit immediately
    if (push == Vector2.Zero)
        return;

    ResolveCollision(push);
}

/// <summary>
/// Resolve the found collision.
/// </summary>
/// <param name="depth">The collision depth.</param>
private void ResolveCollision(Vector2 depth)
{
    // Get the absolute values
    float absDepthX = Math.Abs(depth.X);
    float absDepthY = Math.Abs(depth.Y);

    if (absDepthY < absDepthX) // Resolve the collision along the Y axis.
        position.Y += depth.Y;
    else // Resolve the collision along the X axis.
        position.X += depth.X;

    // Update the bounds to reflect the new position.
    bounds = CollisionBounds;
}