What color space did that Fuji Frontier print the color patches to build the profile? Was it "Printer Space" or "sRGB"?
This needs to be known if that profile is to be useful for soft proofing. And the Costco printer interface software is different than the Fuji Frontier DLxxx at say another Costco or a Walmart or Walgreens. A photo lab tech at Walgreens couldn't find the tabbed interface to locate selecting one or the other space. I had to get the store manager to find it and set it and her husband ran the local one hour photo now out of business.
And Walmart's photo lab tech said he couldn't find it either and he was moonlighting at Walmart to his primary job as a radiologist at our local hospital.
This not being able to choose the space the profile was built from may be what the OP is experiencing when he said the PRINT looked horrible...
Tim, there are several problems with this advice.
Firstly, on building profiles: let's go back to what a profile is supposed to do. It's main task is to characterize how a printer lays down colours in response to the patch values sent to the printer. It needs to do that without the distorting interference of any application managed colour (i.e. only the printer's own colour rendition matters without the original colour data being bent or limited by sRGB, aRGB or whatever). That is why we have applications that send unmanaged data to the printer. The operating system's colour management module needs this printer characterization data for doing the math that will send the printer the colour values needed to get the expected results from it. This is a shorthand way of saying a lot that you can further unpack by reading a book such as Fraser/Murphy/Bunting "Real World Color Management", or Andrew Rodney's "Color Management for Photographers" - both excellent resources.
Secondly, on consistency between machines and labs: the whole point of ICC colour management is to achieve inter-device consistency of results. If the profiles are built correctly as suggested just above and the kind of paper being used is the same or very close (especially as between gloss and matte), if you use the profile bespoke to each printer and the printers are maintained to spec, the outcomes should match pretty closely whatever the location of the lab, the name of the company or the location of the outlet doing the printing.
If you are trying to suggest that some of these photo printing departments aren't profiling their equipment properly or maintaining their equipment to do those two things above mentioned, you have a point - it is a possibility. But I think not necessarily the first place I would go looking for causes of the problems being discussed here, because on the whole, these companies do have adequate colour management resources and advice at their disposal - they need to in order to keep the customers happy, as the customers do not need to be imaging experts to know that blue skies should be blue and green grass green. Most memory colours, especially skin tones and the like, are well known to most people and it's easy to tell whether the prints are in the ball-park. They won't be masterpieces of printing accuracy, but I've been very favourably impressed with the quality of what a Costco photo printing department can produce, on more than one occasion. So I think the causes of the issues here are elsewhere.