Can the Diamond Problem be really solved?

C# has explicit interface implementation to partially deal with this. At least in the case where you've got one of the intermediate interfaces (an object thereof..)

However what probably happens is that the AmphibianVehicle object knows whether it is currently on water or land, and does the right thing.

In your example, move() belongs to the Vehicle interface and defines the contract "going from point A to point B".

When GroundVehicle and WaterVehicle extend Vehicle, they implicitly inherit this contract (analogy: List.contains inherits its contract from Collection.contains -- imagine if it specified something different!).

So when the concrete AmphibianVehicle implements move(), the contract it really needs to respect is Vehicle's. There is a diamond, but the contract doesn't change whether you consider one side of the diamond or the other (or I would call that a design problem).

If you need the contract of "moving" to embody the notion of surface, don't define it in a type that doesn't model this notion:

public interface GroundVehicle extends Vehicle {
    void ride();
}
public interface WaterVehicle extends Vehicle {
    void sail();
}

(analogy: get(int)'s contract is defined by the List interface. It couldn't possibly be defined by Collection, as collections are not necessarily ordered)

Or refactor your generic interface to add the notion:

public interface Vehicle {
    void move(Surface s) throws UnsupportedSurfaceException;
}

The only problem I see when implementing multiple interfaces is when two methods from totally unrelated interfaces happen to collide:

public interface Vehicle {
    void move();
}
public interface GraphicalComponent {
    void move(); // move the graphical component on a screen
}
// Used in a graphical program to manage a fleet of vehicles:
public class Car implements Vehicle, GraphicalComponent {
    void move() {
        // ???
    }
}

But then that wouldn't be a diamond. More like an upside-down triangle.

What you're seeing is how violations of the Liskov Substitution Principle make it really hard to have a working, logical object-oriented structure.
Basically, (public) inheritance should only narrow the purpose of the class, not extend it. In this case, by inheriting from two types of vehicles you are in fact extending the purpose, and as you noticed, it doesn't work - move should be very different for a water vehicle than for a road vehicle.
You could instead aggregate a water vehicle and a ground vehicle object in your amphibious vehicle and decide externally which of the two will be appropriate to the current situation.
Alternatively you could decide that the "vehicle" class is needlessly generic and you'll have separate interfaces for both. That doesn't solve the problem for your amphibious vehicle on its own though - if you call the movement method "move" in both interfaces, you'll still have trouble. So I'd suggest aggregation instead of inheritance.