What is the difference between 我们的新同事 and 我们新的同事 ？
The first is idiomatic; the second, while not wrong per se, isn't commonly used and sounds a bit unnatural. You can also take out the 的 altogether, which will sound informal, but this isn't common across all regions (e.g. north and south China).
I'm not positive, but I don't think you can leave out the 的 between 我们 and 新.
I have the same question as Geoffrey.
I am a bit confused about how to process this sentence. Could anyone clarify?
王先生 = Mr. Wang (name of a man)
是 = is
我们的 = our
新 = new
同事 = colleague