Sau mùa giải 2006-2007 không được HLV Ronald Koeman trọng dụng ở PSV Eindhoven, Lee Nguyễn phải đầu quân cho Randers FC ở giải vô địch quốc gia Đan Mạch. Sự thay đổi này là để anh có cơ hội ra sân nhiều hơn, duy trì hy vọng được triệu tập vào đội tuyển Mỹ và tuyển Olympic Mỹ dự Thế vận hội Bắc Kinh 2008.
Với 23 trận ra sân cho Randers mùa 2008, dù chưa phải là trụ cột ở đội bóng, Lee Nguyễn đã cho thấy khả năng thích nghi nhanh mới môi trường bóng đá mới, nhất là với một cầu thủ mới 22 tuổi. Tuy nhiên, phong độ tốt ấy cũng không đủ giúp anh đạt mục tiêu giữ chỗ ở các cấp độ đội tuyển Mỹ vì sự thất hứa của HLV Bob Bradley.
"Nếu không có lời cảnh báo của Bob Bradley, Lee Nguyễn vẫn chịu khó ở lại PSV Eindhoven, như Ibrahim Alfellay vì HLV Koeman sau đó không lâu đã bị sa thải. Tuy nhiên, khi đá cho Randers và được ra sân nhiều hơn, Bob Bradley vẫn không gọi Lee vào tuyển Mỹ cũng như Olympic Mỹ.
Thay vào đó, ông ta tạo điều kiện cho con trai Micheal Bradley. Việc không được tham dự Olympic Bắc Kinh khiến Lee vô cùng tiếc nuối, vì nó đã cố gắng làm mọi thứ rồi", ông Nguyễn Văn Phẩm, cha Lee Nguyễn, kể lại với VnExpress.
Theo ông Phẩm, năm 2007 sở dĩ HLV Bradley gọi Lee Nguyễn vào tuyển Mỹ là vì sức ép lớn từ danh tiếng của PSV Eindhoven mà Lee Nguyễn đang đầu quân. Con trai ông này, Micheal Bradley, lúc đó mới đầu quân cho Heerenveen - một đội bóng khác cũng ở giải vô địch Hà Lan nhưng kém xa PSV về danh tiếng. Và khi Lee Nguyễn sang Đan Mạch, chơi cho một đội còn ít tiếng tăm hơn, anh bị gạch tên, dù đá nhiều.
Tuyển Olympic Mỹ tham dự Thế Vận Hội 2008 với 21 cầu thủ, trong đó 13 người chơi bóng ở giải nhà nghề Mỹ (MLS) và tám cầu thủ trẻ khác đang đá ở châu Âu, bao gồm Micheal Bradley.
Từ quyết định bất công và sự thiếu minh bạch của HLV Bradley, bằng nhận định của từng trải và người làm cha, ông Phẩm tin rằng Lee Nguyễn sẽ không có cơ hội thi đấu cho tuyển Mỹ chừng nào nhà cầm quân này còn tại vị. Trong giới bóng đá ở Mỹ, cùng với Bruce Arena, Bob Bradley có quyền lực rất lớn. Hai ông này được coi như “đại bàng” của bóng đá xứ cờ hoa.
Về phần Lee Nguyễn, khi xin phép lãnh đạo Randers về Việt Nam một tuần theo lời mời của HAGL, tiền vệ này vẫn chưa hề có ý định thi đấu ở V-League. "Ý định về Việt Nam phần lớn là của cha tôi. Cha tôi sinh ra và trải qua những năm tháng niên thiếu ở Việt Nam nên ông rất tha thiết với quê nhà. Ông muốn tôi về chơi bóng ở mảnh đất đó, ông thực sự vui mừng và hãnh diện khi tôi về Việt Nam", Lee Nguyễn tâm sự.
"Bầu Đức thì rất nồng nhiệt, ông ấy khẩn khoản với tôi rằng cứ về Việt Nam một tuần chơi cho biết chứ không cần phải ký hợp đồng gì cả, cứ coi như về Việt Nam du lịch vậy".
Ông Nguyễn Văn Phẩm nói thêm: "Tôi muốn mang Lee Nguyễn về Việt Nam cũng bởi vì tôi đọc báo và thấy nhiều người cứ nói rằng người Việt Nam nhỏ con nên không chơi bóng đá giỏi được. Tôi muốn chứng minh điều ngược lại là nếu người Việt chơi bóng kỹ thuật, thông minh và nhanh nhẹn thì vẫn có thể hơn được người da trắng".
Tối ngày 8/12/2008, Lee Nguyễn bay từ Đan Mạch đến Sài Gòn và ngay lập tức bầu Đức điều máy bay rước cầu thủ mà ông rất khát khao lên Pleiku. Chiều ngày 9/12, dù trải qua thời gian bay dài và không hề được nghỉ ngơi, Lee Nguyễn đã xỏ giày ra sân thử việc, khi HAGL đá giao hữu với Bình Định.
Chỉ có vòng 45 phút anh nã ba bàn vào lưới Bình Định, khiến không chỉ bầu Đức mà cả dàn cầu thủ hai đội đều choáng ngợp.
Lee Nguyễn không tiết lộ số tiền chính xác ấy bao nhiêu và ông Nguyễn Văn Phẩm cũng từ chối cung cấp thông tin, dù chuyện đã xảy ra sáu năm.
Tuy nhiên, nếu căn cứ vào mức lương 250.000 đôla mỗi năm mà Lee Nguyễn đang nhận được từ Randers FC, có thể hình dùng số tiền “điên rồ” mà bầu Đức chìa ra khiến cha con Lee Nguyễn có thể còn lớn hơn cả bản hợp đồng nửa triệu đôla mà Lee Nguyễn nhận được từ hãng Nike.
Ngày 17/1/2009, Lee Nguyễn chính thức đặt bút ký hợp đồng ba năm và ra mắt trong màu áo HAGL tại khách sạn Rex. Bầu Đức hôm đó cho biết Lee Nguyễn nhận lương tháng 10.000 đôla và tự tin rằng "98% HAGL sẽ vô địch V.League 2009". Tuy nhiên khoản tiền "lót tay" thực sự thì cho đến nay vẫn chưa ai biết chính xác.