Replacing the parameter name in the Body of an Expression

The simplest approach here is Expression.Invoke, for example:

public static Expression<Func<T, bool>> AndAlso<T>(
    Expression<Func<T, bool>> x, Expression<Func<T, bool>> y)
{
    return Expression.Lambda<Func<T, bool>>(
        Expression.AndAlso(x.Body, Expression.Invoke(y, x.Parameters)),
        x.Parameters);
}

This works fine for LINQ-to-Objects and LINQ-to-SQL, but isn't supported by EF. For EF you'll need to use a visitor to rewrite the tree, sadly.

Using the code from: Combining two lambda expressions in c#

public static Expression<Func<T, bool>> AndAlso<T>(
    Expression<Func<T, bool>> x, Expression<Func<T, bool>> y)
{
    var newY = new ExpressionRewriter().Subst(y.Parameters[0], x.Parameters[0]).Inline().Apply(y.Body);

    return Expression.Lambda<Func<T, bool>>(
        Expression.AndAlso(x.Body, newY),
        x.Parameters);
}

Or in .NET 4.0, using ExpressionVisitor:

class ParameterVisitor : ExpressionVisitor
{
    private readonly ReadOnlyCollection<ParameterExpression> from, to;
    public ParameterVisitor(
        ReadOnlyCollection<ParameterExpression> from,
        ReadOnlyCollection<ParameterExpression> to)
    {
        if(from == null) throw new ArgumentNullException("from");
        if(to == null) throw new ArgumentNullException("to");
        if(from.Count != to.Count) throw new InvalidOperationException(
             "Parameter lengths must match");
        this.from = from;
        this.to = to;
    }
    protected override Expression VisitParameter(ParameterExpression node)
    {
        for (int i = 0; i < from.Count; i++)
        {
            if (node == from[i]) return to[i];
        }
        return node;
    }
}
public static Expression<Func<T, bool>> AndAlso<T>(
      Expression<Func<T, bool>> x, Expression<Func<T, bool>> y)
{
    var newY = new ParameterVisitor(y.Parameters, x.Parameters)
              .VisitAndConvert(y.Body, "AndAlso");
    return Expression.Lambda<Func<T, bool>>(
        Expression.AndAlso(x.Body, newY),
        x.Parameters);
}