A "roaming package" aka a billing add-on, just reduces the cost of roaming - it doesn't enable the facility itself. Equally you mention "check the settings" - which specific settings have you checked? Many people confuse the "data roaming" option on their phones, which again - just enables mobile data use whilst roaming.
The relevant setting is an account-level one, and it's enabling international roaming on your account - this unlocks access to foreign networks and thus coverage abroad. As per the previous reply, did you text ROAMING to 150 before leaving the UK?
