Have you tried calling .SaveOrUpdateCopy()?
It should work in all instances, if there is an entity by the same id in the session or if there is no entity at all. This is basically the catch-all method, as it converts a transient object into a persistent one (Save), updates the object if it is existing (Update) or even handles if the entity is a copy of an already existing object (Copy).
Failing that, you may have to identify and .Evict() the existing object before Attaching (.Update()) your "new" object.
This should be easy enough to do:
IPersistable entity = Whatever(); // This is the object we're trying to update
// (IPersistable has an id field)
session.Evict(session.Get(entity.GetType(), entity.Id));
session.SaveOrUpdate(entity);
Although the above code could probably do with some null checking for the .Get() call.