Here are hints to the identities of the celebrities for each of the phone numbers:

1. A Singer
2. A U.S. Senator and Presidential Candidate
3. A Rapper
4. An N.B.A. Basketball Player
5. A Talk Show Host

6. A Home Improvement Guru
7. A Fight Promoter
8. A Womanizer
9. A Major League Baseball Catcher
10. A Singer

11. An Actress
12. A Congressman and Presidential Candidate
13. A Runner
14. A Florida Governor
15. A Radio Talk Show Host

16. A Maryland Basketball Star
17. A Tennis Player
18. A TV Show Airplane Pilot
19. A Major League Baseball Pitcher
20. An N.B.A. Basketball Player

E.C. 21. This would have been Elvis' Phone Number