Where can I purchase large, soft-sided luggage that rolls on four
wheels, in the manner that was popular just before the latest trend of
2 wheels and a handle came in?

Hi Dove!

Below you will find some large, soft-sided luggage that rolls on four wheels.

Samsonite Epsilon  28" Wide Pullman
Dimensions: 20" x 12" x 28" 
Capacity: 6720 cubic inches 
Fabric: 600 Denier Polyester 
Color(s): Black
List Price: $150.00 
Our Price: $89.95 
Sale: $44.95
http://www.pointshop.com/Mall/Catalog/Product/ASP/product-id/676325/store-id/1000012061.html

You may also order this Samsonite Epsilon suitcase from Howard Luggage.
http://www.howardluggage.com/IBS/SimpleCat/Browse.asp?PRODUCT_NAME=epsilon


Prime Horizontal 32" Soft Suitcase
Price:  $99.95 
Materials: Polyester 
Dimensions: 25.5" H x 9.75" W x 32" L
http://www.luggagepoint.com/luggage_specific.asp?cat_id=1&brand_id=52&prod_id=581


Prime Horizontal 30" Soft Suitcase
Price:  $79.95
Use the luggage strap as a 4 wheel pullman 
7 roller wheels on bottom of suitcase for easy maneuverability 
Warranty: 5 Years - Manufacturer 
Materials: Polyester 
Dimensions: 24" H x 9" W x 30" L
http://www.luggagepoint.com/luggage_specific.asp?cat_id=1&brand_id=52&prod_id=580


Here are some sets that might interest you:

Sets

3-piece 1200d wide body Pullman suitcase
Set includes 28", 30", 32" 1200 denier poly-canvas Pullman with strap,
wheels and hard handle.
Regular price: $189.99Sale price: $94.99
http://store.yahoo.com/tennyson/3piec12widbo.html

3-piece 1200d wide suitcase with  silver zipper
This big silver zipper arounded nice looking luggage set. Includes 28"
30" 32" 1200 denier poly-canvas pullman with strap, extra big wheels
and hard handle. Regular price: $219.99Sale price: $109.99
http://store.yahoo.com/tennyson/luggage.html


3-piece tapestry wide body Pullman suitcase
Set includes 32", 30", 28" is crafted from stain and water-resistant
jute tapestry with strap, wheels and hard handle.
Regular price: $149.99Sale price: $74.99
http://store.yahoo.com/tennyson/3piectapwidb.html


3-piece PVC Wide Luggage
Set includes 28" 30" 32" Pullman with strap, wheels and hard handle.
Full top frames and extra wide body makes more stronger and more room
to pack all your belonging.
Regular price: $149.99Sale price: $74.99
http://store.yahoo.com/tennyson/3piecpvcwidl.html


I hope this helps!

Search terms used:
Soft horizontal luggage
Soft Pullman suitcase
Pullman luggage wheels


Best Regards,
Bobbie7-ga

This was remarkable--I had earlier searched the web to no avail at
all.  (My exhaustion and tired eyes were the only result.)  This
answer was wonderfully thorough.  I felt it was a very considerate as
well as an accurate answer to provide a number of options, and all
with good details and websites.  Thank you very much.

Thank you for the kind words, five stars and nice tip!
--Bobbie7