As artificial intelligence (AI) becomes more embedded in personal health technology, its potential to transform health decision-making through personalised recommendations is becoming significant. However, there is limited understanding of how individuals perceive AI-assisted decision-making in the context of personal health. This study investigates the impact of AI-assisted decision-making on trust in physical activity-related health decisions. By employing MoveAI, a GPT-4.0-based physical activity decision-making tool, we conducted a mixed-methods study and conducted an online survey (N=184) and semi-structured interviews (N=24) to explore this dynamic. Our findings emphasise the role of nuanced personal health recommendations and individual decision-making styles in shaping trust in AI-assisted personal health decision-making. This paper contributes to the HCI literature by elucidating the relationship between decision-making styles and trust in the AI-assisted personal health decision-making process and showing the challenges of aligning AI recommendations with individual decision-making preferences.