@JakeyBoy
Check if the linked Power Automate Flow has any Actions which are for Premium only. The Premium might be triggered by the linked Flow having Premium only Actions (although I doubt it, since you might not have been able to add them yourself either in the first place). If someone else is helping you with building this out, maybe they are able to add Premium Connectors in there - check for it in case.
Check if something like DocuSign shows up anywhere. If it is, you need Premium to use Connectors like DocuSign.
Also check and make sure some other developer did not place a Custom Connector or Premium Connector and associated it inside of your App somewhere, or a Power Automate Premium Action.
Test also with:
1. if possible, also go to https://us.flow.microsoft.com/ open your linked flow save a new Copy of the linked Flow with a new name using Save As. Now delete the original Flow. Now go to make.powerapps.com open App for editing, go to Save As, and then give a new name to the App. Then in the clone, check if without the Flow (take out the functionality for now) share this cloned app with the other user, check if they still get the prompt for Premium.
2. If they get the prompt for Premium trial anyway, in same clone check carefully all Data Sources, really be sure somehow a Premium Connector or Custom Connector didn't get in there somehow - if one did, get rid of those save republish and retry.
3. If this works, try re-linking the Flow. If you have an issue only after relinking Flow, check the Flow carefully, and repeat steps 1-3 all over again if simply deleting the Action and saving the Flow doesn't work.
4. If Step 3 gives a problem, link a dummy Flow with almost nothing in it - see if that by itself works in lieu of Step 3 above - then try the real Step 3 after that.
Keep in mind one more thing. If you have Dataverse, I believe according to https://go.microsoft.com/fwlink/?linkid=2085130 the M365 or O365 plans do not have any use rights for Dataverse. Some licenses may have limited use rights for "Dataverse for Teams" but to my knowledge no use rights at all for "Dataverse". If somehow a "Dataverse" Table was added to the data source, this would probably also trigger the prompt for Premium. If this happens, remove all such Tables from the App under Data Sources, republish and see if this helps. If you have Dataverse for Teams table - for troubleshooting take all of those out too and see if it works without such Tables in the App.
Also try clearing all browser cache and cookies from the user's device who got the prompt to start Premium trial - have them also close the browser fully, open it again, sign in again, and see if after they still get the prompt.
Check if above helps @JakeyBoy
If really nothing works at all to resolve it, maybe there is some sort of bug or problem, perhaps you can start a Microsoft support ticket at https://admin.powerplatform.microsoft.com/support maybe you can get more specific and tailored help that way with a support engineer.