Yes, the replace method is the right way to solve this problem. Just remember to override equals on your value objects appropriately!
(This assumes calculating newValue is relatively cheap and collisions are relatively rare. If it's an intensive calculation and collisions are common, it may be worthwhile to introduce a mutex and serialize the calculations.)
It is probably better to re-submit the job to whatever queue is feeding your threads, or put it into a delayed queue, rather than actually put a worker thread to sleep. Sleeping worker threads is overall sad and lacking in scalability.