It depends on the wheels and load, and without more information on what exactly failed (wood? Screws? Wheel?) it will be hard to give you an answer specific to your problem.
When I built my large worktable, I had 4x4 posts as legs, but they were still too small for the 500lb rated load wheels I wanted to use, so added 2x4's wrapped around the legs to end up with, essentially, 7x7 lumber ends. With glue and screws, it provided plenty of stable surface to use 3" (7.5cm) lag bolts. When the wheels are locked, the table is very strong and stable, and when unlocked it moves easily despite its weight and size.
However, looking at how the table is designed, I believe the main issue is that you are screwing into the endgrain of the wood. Screws don't hold very well into endgrain. So I suggest you attach a 2x4x4 to the leg, with the endgrain parallel to the floor (horizontal). Now you have two 2x4's next to each other - close to a 4x4. One presenting end grain to the floor, the other presenting cross grain to the floor.
Now attach another 2x4x4 flat to the bottom of the leg. You can use screws to go from this flat plate to the cross grain piece without special techniques. Screwing the end leg board to the plate, though, should either use pocket holes from the end grain presenting board into the plate, or using angled screws in either direction (plate to leg, or leg to plate) so that the screw threads have something to grab.
Then choose the largest screws that still fit through the wheels of at least 2" length (throw away the screws that came with the wheels - they aren't going to hold the load) and screw them into the 2x4x4 plate you just attached. Depending on the size and location, you may want to pre-drill holes to avoid splitting.
Also, make sure your wheels are up to the expected loads. You may buy four 100LB (45kg) rated wheels, and assume your table will never support more than 400LB (180kg) of load, but keep in mind that wheel ratings are meant for load directly down, and you'll be placing a lot of dynamic and side loads on the work surface. Depending on your planing direction and the load on the table you could be placing well over 200LB loads on a single wheel. Drop a 100lb object on the table near the corner and the sudden force will certainly exceed 100LB for the wheel underneath. Keep this in mind when choosing wheels.