I have uploaded a quake live map to the workshop and it worked perfectly fine. The only problem was that some textures were missing so I added them to the pk3 and updated the workshop-file. Since then quake live only gives me the standard "Can't find map pro_rings.bsp" line.
The pk3 is in the workshop folder and does have the name pro_rings. And in that pk3 is the pro_rings.bsp inside a map folder.
I tried deleting the workshop entry and recreating it but that didn't help. I don't understand the problem here.