Recommendation systems face a major challenge known as the cold-start problem, which occurs when the system lacks sufficient user interaction data. Thus, there is no basis for a recommendation. Existing approaches, such as co-clustering methods and non-personalized popularity models, often struggle to effectively combine heterogeneous user and item data (categorical user attributes and numerical item ratings) or to capture latent group-level preferences. To bridge this gap, we propose a new clustering-popularity-based model that independently groups users and items using two separate algorithms and integrates them through a popularity measure. Users are clustered using K-Modes based on demographic attributes, while items are clustered separately using either K-Means or Fuzzy C-Means (FCM) based on rating patterns. A rating-aware popularity score is then computed within each item cluster. To generate recommendations for new users, we assign them to the appropriate user demographic clusters and suggest items from the most popular clusters. Experiments on the MovieLens 100K dataset show that the FCM-based variant, ClusterPopRec-FCM, consistently outperforms both a K-Means-based variant (ClusterPopRec-KMeans) and the traditional item-based baseline across all cold-start scenarios (extreme, moderate, and non-cold-start scenarios). In the extreme cold-start scenario, ClusterPopRec-FCM achieved Precision@5=54.65 and DCG@5=1.66, which in comparison to the baseline represents percentage increases of 149.7% and 110.1% respectively, with statistical significance < 0.001. These results show the benefit of soft clustering (FCM) in capturing nuanced item relationships and demonstrate the effectiveness of hybrid models that combine demographic clustering with in-cluster popularity scores. This work offer a effective solution for cold-start scenarios and heterogeneity, allowing advancement in recommendation systems research.