Could It Possibly Be The Labs Fault?

'Can't say I know/understand much about the E-6 process, I just shoot the film and send it in for processing.
So now I get back my rolls of Velvia of mostly gardens, forests, and foliage of various places, the greens are
mostly "muddy" - almost like Kodachrome greens! I've shot Velvia before and it wasn't like these.

It's hard to say with so little information. At this point, the answer has to be, "perhaps; who knows".

It would be helpful if you posted a scan.

Also a photograph of the film showing both edges.

And even better, backlit photographs of the problematic Velvia and the Velvia you are happy with, side by side in the same image, with the edges and sprockets visible.